Michael J. Swart

October 19, 2011

Secret Santa as a Puzzle

Filed under: SQLServerPedia Syndication,Technical Articles — Tags: , , , — Michael J. Swart @ 12:00 pm

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 an of anagrams of a word with n different letters, each occurring twice, with no letters fixed. The desired number of permutations is then 2nan, 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 n1, … ,nr of r different letters is

where Pk is the k-th Laguerre polynomial. In the present case, r=n and ni=2, so we only need the second Laguerre polynomial, which is P2(x)=(1/2)(x2-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.

8 Comments »

  1. Really fun – but as I recall – It was mostly YOU giving only ME a hard time for picking my name over and over again.

    Comment by Dave S — October 19, 2011 @ 1:46 pm

  2. As an anagram nut, I’m preferential to joriki’s answer. As a practical solution, I’d say:

    1. have a neutral 3rd party assign each participant a color.
    2. each participant will submit a slip in assigned color with his/her name on it to the neutral party, or palm it into a bag, or make everyone look away while he/she puts it into a bag
    3. Given bag method, once all slips are entered, dump contents onto a table.
    4. Have everyone pick. Of course, there is some chance the last man standing will be left with his own color if you have an odd number.

    Comment by Claire — October 19, 2011 @ 3:48 pm

  3. Awesome! My family has this problem too. :)

    Comment by Cressa — October 19, 2011 @ 4:35 pm

  4. @Claire, Good job! I think that there is hope for a method like that. That method has a much better chance of working than signing up at Elfster.com. Maybe I’ll see if my family will be up for that.

    Comment by Michael J. Swart — October 19, 2011 @ 4:55 pm

  5. Our family does a yankee swap rather than Secret Santa. The only problem with that from my point of view is that the process takes forever with more than 5 people involved.
    “who’s got 15, you’re next! 15? 15?”
    “Oh! that’s mine, sorry. Let’s see, which one [of the 5 remaining packages] will I pick … this one? Nah … hmmmmm”
    “Pick one!!”
    By this time, the beer’s all gone, people are getting cranky and wanting to go home … you get the picture. :-)
    Plus there’s the fun of getting the crappy gift or worse, your own. :-)

    Comment by Bob — October 24, 2011 @ 3:39 pm

  6. I hear you Bob. It can be pretty rough if #12 went out for a smoke with #19 and people insist on waiting for them.
    And then you open a gift that’s a paperback, but it turns out to be Dan Brown, and nobody will steal it from you.
    Have some more egg nog :-) Cheers.

    Comment by Michael J. Swart — October 24, 2011 @ 4:53 pm

  7. I just did an article on Permutations in SQL. It is not published yet.

    Think about this approach; a couple gets a prime integer id, (n) and the husband is assigned (+n) and the wife is (-n). Thus a gift pair that totals to zero is illegal. The toal of a permutation should also be zero.

    It also makes the “boy gift/girl gift” rules easier, if you play with them (each gender is required to buy gifts for that gender or the other one).

    Comment by Joe Celko — October 25, 2011 @ 1:25 am

  8. Hi Joe,
    Wow, as a practical suggestion, “The boy gift/girl gift” rules reduce the average number of picks for five couples from 36.8 to 18.7!
    That is a suggestion that would work for my family.

    Can’t wait for the article. Cheers.

    Comment by Michael J. Swart — October 25, 2011 @ 2:09 pm

RSS feed for comments on this post. TrackBack URL

Leave a comment

Powered by WordPress