Christmas Algorithms

It doesn't matter how sincere it
is, nor how heartfelt the spirit.
Sentiment will not endear it;
what's important is.. The price!

— A Christmas Carol, by Tom Lehrer.

The holiday season is coming up again, and that means.. Gift giving! And with that comes, of course, drawing lots in order to assign gift recipients to gift buyers.

In my family we solved that problem years ago, with a little C# program which randomly assigns people to each other, making sure of course that nobody gets assigned to themselves, and which displays the results through a simple GUI in such a way that nobody gets to know anything other than the name of the recipient assigned to them. The algorithm is rather brute-force: For every buyer, randomly choose a recipient; if the buyer-recipient combination is valid, assign them to each other, otherwise choose again. "Valid" is defined as: the buyer must not be the same as the recipient, and the recipient must not already be assigned to another buyer. Simple and effective.

I am quite sure I can prove that this algorithm is fair, meaning that every allowed combination is equally likely. In theory, though, there's a small problem with it, which is that it might run for years before finishing. In practice, however, the algorithm is efficient even for large groups. Assuming a perfectly fair random-number generator, in a group of n people the first iteration of the "for every buyer" loop will find a valid recipient in (n/n-1) attempts on average, the next iteration will find a valid recipient in (n/n-2) attempts on average, and so on. So the average total running time of the program will be O(n*n), which is good enough for our purpose. The program's running time could easily be made deterministic, of course, by looking only in the pool of valid recipients to begin with.

My friend Dirk-Jan Binnema is currently wrestling with the same problem, but he chose a different approach: first shuffle the group of people into a random order, then let each person buy a gift for the next person in the sequence (treating the sequence as cyclical). This is certainly a more elegant algorithm than mine (whether or not it is easier to implement depends somewhat on whether your programming environment offers an "array shuffle" function, or a fast way to hack one up — see his post for a nice one-liner in Ruby).

In addition to the obvious requirement of not assigning people to themselves, Dirk-Jan adds a second requirement of not creating pairs of people assigned to each other. He then proves that his algorithm satisfies both requirements.

I would argue, however, that the algorithm does not satisfy another important requirement: fairness. By fairness, I mean that every allowed combination of assignments should be equally likely. The "shuffle and sequence" algorithm does not satisfy this requirement. For example, in a group of six people, the outcome [1-2, 2-3, 3-1, 4-5, 5-6, 6-4] is not possible. In fact, the only possible outcome of this algorithm is a single unidirectional cycle.

Therefore, I think I'll stick to my nested-loop implementation for now. Besides, I lost the source code.