Aw, nuts... Funster-mostly-lurker Thomas Colthurst and I spent a little time this afternoon thinking about how good my secret santa algorithm is. (Recall, it's iterating "remove two envelopes from the hat, swap the names inside, then put one of them back in the hat.") After some amount of mental fumbling, we realized the sad truth: turns out that it generates only n-cycles. :-( Once you realize it's true, the proof's not hard, so I'll leave it as an exercise. Sigh... Anyway, in light of Fred Helenius's observation (that choosing among derangements uniformly is essentially hard for prime factorization reasons), it seems that the next obvious thing to hope for is that, even once you know who you're giving gifts to, the person giving gifts to you should be equally likely to be anyone in the group. It's pretty clear that, if you do a decent job randomizing, there should only be two probabilities to think about: that your gift-giver is (a) the person you're giving gifts to, or (b) someone else. And of course if (a) happens 1/(n-1) of the time, you meet this criterion. Anyway, my algorithm does (a) with probability zero, so unless you're of the camp that says n-cycles are a good thing, a better routine is required. From this point of view, by the way, the "two hats" algorithm (for n even) is also flawed: the person you're giving gifts to was definitely in the opposite hat from you, making them (epsilon more than) twice as likely as anyone else to be your santa. --Michael Kleber kleber@brandeis.edu