We decided to do Secret Santa this year at AetherWorks, and we were all pretty excited about it. We put everyone’s name on a piece of paper, threw them in an empty granola bar box, and everyone picked.
I chose last, and in an unfortunate twist, chose my own name. Undeterred, we threw the names back in and tried again. This time Mike picked his own name. It wasn’t until the third drawing that we all managed to pick someone else, and by then we were frustrated by how difficult a simple Secret Santa exchange was for us to execute. How many software engineers does it take to pull off a gift swap?
Set on absolving the world of the inefficiency that is drawing names out of a hat, the development team told me they could “easily” write a program to perform this task. Each of them wrote a program in a different language that assigned gifters and recipients at complete random, such that no one would be buying for themselves.
Most of them didn’t get it exactly right.
See what they came up with here, and read on for Mike Zaccardo’s explanation of where the others went wrong. Use Mike’s code at the end of this post (the one that does it right!) to set up your own gift exchange and save yourself the frustration of a flawed Secret Santa drawing.
“At first, we each implemented solutions like this:
- Randomly shuffle the list of participants
- Each participant receives a gift from the participant that precedes them in the shuffled list
- Each participant buys a gift for the participant that follows them in the shuffled list
Unfortunately, this algorithm has a flaw – it is unable to generate every possible valid combination of assignments. Specifically, the algorithm cannot produce assignments with loops (where person A has to buy for person B, and person B has to buy for person A), as each participant receives a gift from the preceding participant in the shuffled list and gives a gift to the following participant.
After some thought, I implemented a solution that requires more iteration than my colleagues’ but is able to generate every possible valid combination with a uniform likelihood. The algorithm can be generalized like this:
- Copy the participants into two lists: buyers and receivers
- Randomly shuffle receivers; do nothing to buyers
- Check the value at every position in buyers and make sure that the corresponding value at the same position in receivers is not the same (the buyer is not buying for him/herself)
- Go back to step (2) if the check in step (3) failed; otherwise we’re done!
Step (2) is equally likely to produce each of the possible permutations, but (3) filters them to only the permutations where each buyer does not buy for him/herself. These types of permutations are known as derangements. The algorithm is therefore equally likely to produce each of the possible derangements, the valid sets of assignments!
As I studied the concept of derangements, I discovered that when choosing Secret Santa assignments, regardless of the number of people involved, there is approximately a 63.2% chance that someone will choose him/herself. To see the derivation, click here. Given that probability of failure, it now makes total sense that we needed three attempts to successfully choose assignments.
When you really think about it, my algorithm is fundamentally the same as what our office did manually, just performed really quickly on a computer – pick randomly until a derangement is found. So I guess it turns out that the correct method really is to just pick from a granola bar box!”