I am working on an special version of Secret Santa with internal sub-groups.
Typical Secret Santa (SS) requirements:
- Cannot be assigned to themselves
- Should be random
- Every participant should be assigned to someone
- Every participant should have someone assigned to
Special requirements; there are subgroups that should be taken into consideration:
- Reduce participants assigned to someone into their same group as much as possible (none if possible)
Implementation
I am new to Swift, I am working on a playground. Let's first consider the problems to solve:
Problems to consider
For one group (normal SS)
Let's assume a 3 people group
1->2
2->1
3->?
In that case there is no possible person for 3 to give to.
For multiple groups
Assume these 3 groups group-participant
:
[1-1,1-2]
[2-1]
[3-1]
This could be assigned like this
2-1 -> 3-1
3-1 -> 2-1
1-1 -> 1->2
1-2 -> 1->1
Which is not a desired outcome.
Algorithm
Pick random participant p
from all the possible participants. Also save the first p
apart.
if p is not from the largest group
r is a random element from the largest group
else if p is from the largest group and there are multiple non-empty groups
r is a random element from the any other group
else if p is not from the largest group and is from the only remaining group
r is a random element from its group that it is not p
p gives present to r
Now remove p
from the groups and repeat the same but make p=r
until it is there are no more participants. The last one gives to the first one and the shuffle is complete.
Code
class Participant: CustomStringConvertible {
var name = "noname"
var contact = "nocontact"
var giveTo:Participant?
init(name:String,contact:String){
self.name = name
self.contact = contact
}
var description: String {return name + ((giveTo==nil) ?"":"->\(giveTo!.name)")}
}
class Group: CustomDebugStringConvertible {
static var allGroups:[Group]=[]
static var counter = 0
var participants:[Participant]=[]
var name = "G-x"
var description:String {return name}
var debugDescription:String {return name}
init(participants:[Participant]){
self.participants=participants
name = "G-\(Group.counter++)"
Group.allGroups.append(self)
Group.allGroups = Group.sortGroups(Group.allGroups)
}
func size()->Int{return self.participants.count}
func getRandParticipant()->Participant{
let p = participants[Int(arc4random_uniform(UInt32(participants.count)))]
return p
}
func remove(p:Participant)->Bool{
let originalIndex = participants.count
participants = participants.filter() { $0.name != p.name }
return originalIndex != participants.count
}
static func sortGroups(g:[Group])->[Group]{
//remove groups with size = 0
let rg = g.filter() {return $0.size()>0}
//sort
return rg.sort() {return $0.0.size()>$0.1.size()}
}
static func getRandGroup(groups:[Group])->Group{
return groups[Int(arc4random_uniform(UInt32(groups.count)))]
}
static func removeFromGroups(groups:[Group],p:Participant)->[Group]{
for g in groups{
if(g.remove(p)){
break;
}
}
return sortGroups(groups)
}
static func getPairs(groups:[Group])->[Participant]{
var groups2consume = groups
var giverGroup = getRandGroup(groups2consume)
var searchIn:[Group]
var giver:Participant = giverGroup.getRandParticipant()
let first = giver
var returnArray:[Participant] = []
while(groups2consume.count>0){
let indexO = groups2consume.indexOf() {$0.name==giverGroup.name}
if let index = indexO{
if (index>0){
//if giverGroup is 0 it means it is in the largest group
searchIn = [groups2consume[0]]
}else if groups2consume.count>1{
//if giverGroup is not 0 and the count is >0 then there are smaller groups
searchIn = groups2consume
searchIn.removeFirst()
}else{
//there is only one group left
searchIn = groups2consume
searchIn[0].remove(giver)
}
if searchIn[0].participants.count>0{
let receiverGroup = getRandGroup(searchIn)
let receiver = receiverGroup.getRandParticipant()
groups2consume = removeFromGroups(groups2consume, p: giver)
giver.giveTo=receiver
returnArray.append(giver)
giverGroup = receiverGroup
giver = receiver
}else{
groups2consume = removeFromGroups(groups2consume, p: giver)
}
}else{
break
}
}
giver.giveTo=first
returnArray.append(giver)
return returnArray
}
}
Test
Group(participants:[
Participant(name: "pπ1", contact: "nπ1"),
Participant(name: "pπ2", contact: "nπ2"),
Participant(name: "pπ3", contact: "nπ3"),
Participant(name: "pπ4", contact: "nπ4"),
Participant(name: "pπ5", contact: "nπ5")])
Group(participants:[
Participant(name: "pπ1", contact: "nπ1")])
Group(participants:[
Participant(name: "pπ1", contact: "nπ1"),
Participant(name: "pπ2", contact: "nπ2")])
Group.allGroups
let pairs = Group.getPairs(Group.allGroups);
print("pairs(\(pairs.count)) done \(pairs)")
Output
pairs(8) done [pπ1->pπ1, pπ1->pπ4, pπ4->pπ2, pπ2->pπ2, pπ2->pπ1, pπ1->pπ3, pπ3->pπ5, pπ5->pπ1]