Allan C. Wechsler outlined:
We want to produce a random derangement on N items. Start by figuring out how many such derangements there are; say there are M of them. Select a random number between 0 and M-1. This will be the "index" of the derangement we will generate; call it K. Initialize a variable to K: this is the "residual index", and we will be decrementing it as we leaf through the derangements in a certain order.
Hi, welcome to my branch of math... :-) This is actually pretty straightforward, so it is indeed easy to pick a random derangement. But I still feel like this isn't a satisfactory solution to Marc's original query. First, it requires a real random number generator -- though as Fred Helenius just pointed out, our attempt to use hats instead is to some extent doomed. Second, it gives the players extra information: everyone knows the chosen derangement, just not which people go with which labels. So for example, you know the cycle structure -- and in the n=4 case, e.g, knowing whether you're working with two 2-cycles or one 4-cycle might actually make a difference. But anyway, let me get back to "How to choose a random derangement." Let d(n) be the number of derangements of n things. So d(1)=0, d(2)=1, and thereafter you can calculate d(n) via the recurrence relation d(n) = (n-1) * ( d(n-1) + d(n-2) ) There is also a 1-term recurrence, d(n) = n * d(n-1) + (-1)^n. But the two-term one above is better for our purposes, since it has an easy combinatorial proof: --------- Consider a derangement f : {1...n} -> {1...n}. There are n-1 choices for f(n). Now we want to get rid of n and recurse: a) If f(f(n))=n, i.e. n is in a two-cycle, then the remainder of f describes a derangement of the remaining n-2 items. So there are d(n-2) possibilities. b) Otherwise, we can "elide" thing n to get a derangement of {1...n-1}: have the person who was going to give gifts to n give them to f(n) instead. (We can't elide n in this case, since f(n) would end up giving herself a gift.) --------- This can be easily rearranged into an algorithm for generating a random derangement, and all you need is the ability to pick randomly with the ratio d(n-1):d(n-2). Now of course d(n-1)/d(n-2) is *very close* to n-1, by the one-term recurrence above! (But doing it exactly with hats still runs into the problem Fred Helenius pointed out, of course.) --Michael Kleber kleber@brandeis.edu