Secret Santa for the covid age

Secret Santa is a popular tradition in offices and amongst other groups. The idea is that you buy a gift for another member of the group, assigned to you at random. The secret part is that you don’t reveal who you’re buying the gift for – and therefore, of course, you don’t know who’s buying a gift for you. The way it usually works is that you all put your names into a hat. Everyone takes a name without revealing it to the other members of the group – unless someone pulls their own name out, in which case you put all of the names back in the hat and try again.

But what happens now that everyone is working from home and meeting friends remotely? How do you maintain the tradition?

There are websites that will do it for you. You put in everyone’s email address and they randomly match buyers with recipients, emailing the buyers. A search for “secret santa generator” will return plenty of examples. There’s only one downside – you have to trust a random website with everyone’s email address. I’m not saying any of these sites are dodgy, but they seem like a pretty efficient way to harvest email addresses…

Faced with this dilemma for a group I belong to, I decided to write a program myself.

There are two ways to randomly assign the buyers and recipients. The first is simple and guaranteed to work first time – i.e. noone will ever pull their own name out of the virtual hat. You start off with a list of participants – let’s say Ron, Ginny, Fred, George, Percy, Charlie and Bill – and shuffle the names so that they’re in random order. Each person then buys for the next person on the list – wrapping around so that the last person buys for the first:

This method will always generate a perfectly valid secret santa combination, but a purist will note that it’s not perfect – it can’t generate all possible secret santa combinations. It’s perfectly valid to have mutual pairs of recipients – i.e A buys for B and B buys for A. The simple method can’t generate that kind of combination.

The comprehensive method replicates pulling names from a hat. You start off with the names in a given order. You then create a second list of the names, shuffled into a random order and match them to the original list. Taking the random order from the first example shows the problem – Ron is buying for Ron:

The simplest way to fix that problem in the program is to do what you’d do when drawing names from a hat – just keep trying until you get a valid combination.

How many attempts is that likely to take? While testing my program I decided to find out. I ran it 10,000,000 times on the group of 7 names – obviously without sending the emails! It took about 90 seconds and the worst case took 39 tries – you could be there a while if you’re actually pulling names out of a hat.

On average, though, it took about 2.7 attempts – or, to be more precise, 2.7177598 tries . If you’re interested in maths, that’s a suspiciously familiar number – it’s pretty close to the value of e, which is 2.7182818…. – it’s an irrational number that, like pi, can’t be written down exactly.

So can you work out all of the potentially valid combinations in advance and simply pick one at random? This is where we have to dive in to the maths. The mathematical term for a valid secret santa combination is a derangement:

“In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position. In other words, a derangement is a permutation that has no fixed points.”

There are ways to estimate the number of derangements, but to list them all you have to list all of the possible combinations and eliminate the ones that aren’t valid. The total number of combinations is n! (n factorial), where n is the number of elements in the set. A group of seven members can be combined in 5040 different ways.

It turns out that the number of those combinations that are derangements is approximately n!/e – which works out at roughly 1854. That’s where the number e comes into it – if there are n!/e derangements, then the chances of a randomly selected combination being a derangement is 1 in e – i.e. roughly every 2.72 tries, which is pretty much exactly what I got. Over an even larger number of runs, the average number of draws required to find a valid combination – a derangement – will tend towards e.

Putting the maths to one side, the core algorithm for the program is pretty simple. I wrote it in Python, and the random library has a handy shuffle method that I could use to shuffle the list of names. You start off with two identical lists of names – buyers and receivers – and then look for  a valid draw, storing the results in a dictionary of key/value pairs for buyer and recipient:

import random

buyers = ['Ginny', 'Ron', 'Fred', 'George', 'Percy', 'Charlie', 'Bill']
recipients = buyers.copy()

valid = False

while not valid:
    results = {}
    random.shuffle(recipients)
    valid = True
    for i in range(len(buyers)):
        if buyers[i] == recipients[i]:
            valid = False
            break
        results[buyers[i]] = recipients[i]

for buyer in results: 
    print("{} is buying for {}".format(buyer, results[buyer]))

The bulk of my actual program was all of the stuff outside of the core algorithm – reading the names from a file, generating the output, and sending the emails. In order to maintain the secrecy, I didn’t output the results to screen or email myself the full list.

It was also fortunate that I have an email account that I could use. Sending email via SMTP is easy to do as long as your email provider still allows for it. In these days of higher security and two factor authentication, that’s not a given. Gmail, for example, requires you reduce your security settings in order to use SMTP.

Luckily my rarely used ISP account still supports SMTP without jumping through any extra hoops, but otherwise it might be worth setting up a secondary account to use for less secure apps.

I added a few little niceties to the code, such as debug options for test runs and the option to send the full list of buyers and recipients to another email address – useful if you know someone who isn’t participating but is willing to act as a coordinator in case anyone loses their email and needs a reminder.

I also added an option to run the draw multiple times, just to gather some stats so that you can see how many attempts it takes, on average, to get a valid draw. It’s also a nice little single core performance test. It’s also a performance test of Python implementations. On my PC, 10,000,000 draws took 90s when running the Linux version of Python on the Windows Subsystem for Linux. Using Python for Windows it took 172s – not far short of twice as long.

There are some enhancements I might consider for next year. For example, it would be nice to be able to pull in the previous year’s draw so that nobody has to buy for the same recipient two years in a row.  I wonder how that changes the maths? How many draws would be required to get a valid draw that gives everyone a different recipient to last one?

I’ve put the full code on Github if you want to try it for yourself. For more on the maths, there’s a Numberphile video that explains derangements in more detail.

in Code

Related Posts

Add a Comment

Your email address will not be published. All comments will be reviewed.

This site uses Akismet to reduce spam. Learn how your comment data is processed.