Author: Richard Carter, Data Scientist at The Data Lab
Here at The Data Lab we love Data Science so much, we couldn’t even let Christmas celebrations go without it. In this blog post, Richard Carter explains how he organised this year’s Secret Santa at The Data Lab, using Python and derangements.
It’s been a long, long time since I’ve worked in a corporate environment; twelve years in fact. To put that into context that’s before the arrival of Facebook (2004), before the first ever Twitter tweet (2006), and at a time when the iPhone (2007) was ne’er yet a glimmer in Steve Jobs’ eye. Memories of offices past have started to fade save for the odd exception, like the time when a colleague ran a sweepstake on how long our boss was going to take on the toilet.
Thankfully times have changed, and one of the common features of the modern workplace is the running of a Secret Santa at Christmas. For those that haven’t heard the term before the idea is for all participants to be assigned a recipient at random for whom they buy a present anonymously. This is usually facilitated by the drawing out of names written on paper.
It turns out that such a simple concept actually contains some very interesting mathematics from the branch known as combinatorics. This area deals with a whole range of problems around “counting”, such as working out how many possible distributions of the cards there are in the game of bridge, or how many equivalent routes there are between two locations in a New York-style grid system.
To understand how combinatorial mathematics manifests in a Secret Santa we first need to define a permutation. This is an ordering (or reordering) of a set of items. To illustrate, suppose we have a workforce consisting of a Jack, a Queen and a King. The permutations of these are JQK, JKQ, QJK, QKJ, KJQ, and KQJ. For a general set of n items there are a total of n! (pronouned “factorial n”) permutations, given by nÃ(n1)Ã…Ã1.
Given a list of the employees and a random permutation of them we can place them side-by-side to give a mapping of giver to recipient for the regal Secret Santa. However, the issue with this method can be seen in the following case. When it comes to handing out presents the King ends up giving himself one!
| Giver | Recipient |
|---|---|
| Jack | Queen |
| Queen | Jack |
| King | King |
Rather than a permutation of the employees it turns out that what we require is a derangement. This is a permutation over a set such that no element maps to itself. The number of derangements of a set of size n, usually written !n (“subfactorial n”) is given by:
where e is the base of the natural logarithms (approximately 2.718) and [x] rounds the division to the nearest integer. Hence as n only around 37% of the permutations are derangements suitable for our Secret Santa.
The Python code below takes as input a list of names, creates a derangement of them, then prints out a pairing of (giver, recipient) for all employees.
For more information check out the Wikipedia page on derangements and the academic paper by Merlini, Sprugnoli and Verri on which the above code is based.
