[math-fun] Secret Santa -> random derangements
As seems to be my style recently, I'm not going to actually develop an algorithm for random derangements, but instead will suggest the outline of one in the hopes that some energetic funster will do all the hard work. 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. (Eudora's spell-checker doesn't like "decrementing" (or "Eudora's"!).) Element 0 can go to 1, 2, ... M-1. Calculate the number of derangements that take 0 to 1. If this number is less than or equal to the residual index, decrement the residual index by this amount. Now calculate the number of derangements that will take 0 to 2. Repeat this process until the number of derangements that takes 0 someplace is less than the residual index, and nail that sucker: 0 will go to that place, which we may call 0'. Now we must decide where to put 1. Calculate the number of derangements that take 0 to 0' and 1 to 0. If this number is less than the residual index, decrement the residual index and go on to the next legal place that 1 can go. These legal places will be everywhere except 1 and 0'. Eventually we will decide on a 1', because the number of derangements that take 0 to 0' and 1 to 1' will be greater than the residual index. Similarly, we decide on 2', 3', 4', and so on; eventually we will reach a point where the residual index is 0 and everything else is forced. (The code probably won't have to notice this specially, this being one of those examples of something that looks like a special case to a human, but is just business as usual to a program.) Essentially we have invented a numbering scheme for derangements, and it is blatantly clear that all derangements have an equal likelihood of being picked. Missing from this description is the algorithm for calculating the number of derangements with some values given; I do not know how hairy such a procedure is. In is conceivable that there is another, simpler, more elegant technique, but the recent observation about factorizations of derangement censuses gives me an intuition that this will be hard to find. -ACW
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
participants (2)
-
Allan C. Wechsler -
Michael Kleber