Michael J. Swart

So every year, the adults in my family pick names to do a gift exchange. I guess lots of people do this and they call it Secret Santa.

In my family there are five couples that participate and we draw names from a hat. Inevitably, someone will draw their own name or the name of their spouse and everyone puts the names back in the hat. It usually takes us quite a few tries before we get it right.

This past thanksgiving (Canadian) we went through this again. It’s fun and we always give the person who picked their own name a hard time. But I got to thinking about this as a puzzle:

“How can we exchange names fairly and secretly without the do-overs?”

Well, let’s look at this a few ways:

• As a mathie.
• As a computer techie.
• From a practical point of view.

As a Mathie

I graduated from University of Waterloo with a BMath with a major in CS and C&O*. But since graduating, I’ve focused only on CS (Computer Science) things. The mathie in me wonders: “What are the odds that we pass the hat around successfully?”

I thought long and hard about it but couldn’t crack that question. My textbooks were no help and there were no professors on hand to answer, so I asked http://math.stackexchange.com for help. Hoping that I’d have just as much success with that site as I do with stackoverflow.com. I was not disappointed. Here’s the question I asked:

Five couples draw names from a hat. If a person draws their own name, or the name of their spouse, all the names go back in a hat and names are re-drawn. Using a computer, I know that the probability of this happening is 1 – (440192 / 10!) or about 88%. What’s a general expression for n couples?

And a stackexchange user joriki gave a brilliant answer:

By assigning a letter to each couple, this can be reduced to the problem of finding the number a_n of anagrams of a word with n different letters, each occurring twice, with no letters fixed. The desired number of permutations is then 2ⁿa_n, since each of the n couples can be assigned in two ways to the two instances of its letter. Wikipedia mentions this problem as a generalized derangement problem. The general formula given for a word with numbers n₁, … ,n_r of r different letters is

where P_k is the k-th Laguerre polynomial. In the present case, r=n and n_i=2, so we only need the second Laguerre polynomial, which is P₂(x)=(1/2)(x²-4x+2). The n factors of (1/2) cancel with the n factors of 2, so the probability of success is

where (2n)! counts the total number of permutations. For n=5, Wolfram|Alpha gives 440192/(10!), as you calculated.

I think it’s a beautiful answer and for the first time in a long time, I missed doing Math. So this math problem and the probabilities are now well understood. But it doesn’t save any time picking names at Thanksgiving does it? Let’s look at it from another point of view.

As a Computer Techie

Using C#
Okay, I understand this subject much better. A C# program is easy to write. In fact, I wrote a quick one and it looks something like this:

static void Main()
{
	List<string> names = new List<string>() {"Mike", "Leanne", "Dave S",
		"Cindy", "Marianne", "Dave B", "Linda", "Matt",
		"Lisa", "Dan" };
 
	List<int> picks = new List<int>() { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 
	while (!IsValid(picks))
	{
		Shuffle(ref picks);
	}
 
	PrintResults(picks, names);
}

You can look at the full program here. It works, but it doesn’t feel like the right solution to the problem: The results aren’t secret for one thing. We’d need a trusted third party to distribute the results. Also notice the while loop, we don’t know for certain if/when the while loop will break, so this program seems a little sloppy.

Using SQL
So now here’s a subject I’m really really comfortable with. I used an approach that my friend Paul Santos explained to me when we talked about this problem. His approach is this:

• Drawing from a hat is a permutation of 10 names. So generate all the permutations
• Filter out the invalid permutations
• Pick a random permutation from the list of valid ones and report that

So here’s me showing all the permutations:

with OneToTen AS
(
	SELECT n
	FROM (VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),(10)) as N(n)
)
SELECT A.n, B.n, C.n, D.n, E.n, F.n, G.n, H.n, I.n, J.n
FROM OneToTen A
JOIN OneToTen B
	ON B.n NOT IN (A.n)
JOIN OneToTen C
	ON C.n NOT IN (A.n, B.n)
JOIN OneToTen D
	ON D.n NOT IN (A.n, B.n, C.n)
JOIN OneToTen E
	ON E.n NOT IN (A.n, B.n, C.n, D.n)
JOIN OneToTen F
	ON F.n NOT IN (A.n, B.n, C.n, D.n, E.n)
JOIN OneToTen G
	ON G.n NOT IN (A.n, B.n, C.n, D.n, E.n, F.n)
JOIN OneToTen H
	ON H.n NOT IN (A.n, B.n, C.n, D.n, E.n, F.n, G.n)
JOIN OneToTen I
	ON I.n NOT IN (A.n, B.n, C.n, D.n, E.n, F.n, G.n, H.n)
JOIN OneToTen J
	ON J.n NOT IN (A.n, B.n, C.n, D.n, E.n, F.n, G.n, H.n, I.n)
OPTION (FORCE ORDER, MAXDOP 1)

To filter out the invalid permutations, I add a where clause. To report a random permutation, I order the results by newid() and select the top 1 row:

with OneToTen AS
(
	SELECT n
	FROM (VALUES (1),(2),(3),(4),(5),(6),(7),(8),(9),(10)) as N(n)
)
SELECT TOP (1) A.n, B.n, C.n, D.n, E.n, F.n, G.n, H.n, I.n, J.n
FROM OneToTen A
JOIN OneToTen B
	ON B.n NOT IN (A.n)
JOIN OneToTen C
	ON C.n NOT IN (A.n, B.n)
JOIN OneToTen D
	ON D.n NOT IN (A.n, B.n, C.n)
JOIN OneToTen E
	ON E.n NOT IN (A.n, B.n, C.n, D.n)
JOIN OneToTen F
	ON F.n NOT IN (A.n, B.n, C.n, D.n, E.n)
JOIN OneToTen G
	ON G.n NOT IN (A.n, B.n, C.n, D.n, E.n, F.n)
JOIN OneToTen H
	ON H.n NOT IN (A.n, B.n, C.n, D.n, E.n, F.n, G.n)
JOIN OneToTen I
	ON I.n NOT IN (A.n, B.n, C.n, D.n, E.n, F.n, G.n, H.n)
JOIN OneToTen J
	ON J.n NOT IN (A.n, B.n, C.n, D.n, E.n, F.n, G.n, H.n, I.n)
WHERE A.n NOT IN (1, 2)
	AND B.n NOT IN (1, 2)
	AND C.n NOT IN (3, 4)
	AND D.n NOT IN (3, 4)
	AND E.n NOT IN (5, 6)
	AND F.n NOT IN (5, 6)
	AND G.n NOT IN (7, 8)
	AND H.n NOT IN (7, 8)
	AND I.n NOT IN (9, 10)
	AND J.n NOT IN (9, 10)
ORDER BY NEWID()
OPTION (FORCE ORDER, MAXDOP 1)

So I’m really happy with this. But only as a solution to a puzzle. The only thing it has going for it is that it’s guaranteed to halt. It doesn’t take less cpu than the C# program and we’re further away from telling relatives who they’re meant to buy presents for!

A Practical Point Of View

In real life, using authentication schemes and trusted third parties is a great way to bring any holiday party to a halt Mr. Buzz Killington (No more stuffing for you). So what kind of practical things can you do to make things easier or avoid do-overs? Here’s a couple ideas:

• There are many many websites that are built just for this problem: SecretSanta.com, Elfster, and DrawNames.com. (I’m not making those up!) I think there’s even a facebook or iPhone app for that. I haven’t looked too closely at these so I can’t vouch for them.
• You could write people’s names on an old deck of cards. Shuffle those cards and deal them out. You don’t avoid any problems this way – I mean, you won’t avoid getting your own name – but shuffling and dealing is quicker than passing around a hat.
• If you pick your own name, replace it and pick again. The exchange won’t be 100% secret, but most people don’t care. This is what most Secret Santas are like.
• Status quo. Do nothing. This is probably what my family will stick with. We’ll continue to pass around the hat and give people a hard time for picking their own names.

Have you got any other ideas? If you do a gift exchange with your family, what does your family do?

*~ CS and C&O are short for “Computer Science and Combinatorics and Optimization”, my first year at University was spent learning to pronounce that correctly.