At 11:31 AM 1/9/04, Michael Kleber wrote:
I'll have to think more about whether there's an easy variant that will give uniform distribution to the derangements generated --- without giving out more information.
An observation: A large class of "hat-drawing-like" algorithms-- including most of those proposed in the past day--cannot generate derangements uniformly. If the procedure involves a finite sequence of uniform choices, each from a set of N or fewer objects, the probability of any particular sequence of choices will be 1/K, where K contains no prime factors larger than N. A particular derangement might be generated in many ways, so its probability would be the sum of different 1/K terms, but the total probability still will have no prime factor larger than N in the denominator. Unfortunately, the number of derangements for N = 5 is 44 = 2*2*11, and for N = 6, it's 265 = 5*53; so a prime factor larger than N is needed for the selection to be uniform. There are three obvious ways around this limitation, although it isn't clear how to apply some of them to an algorithm that could be used at a restaurant table. First, allow an unbounded sequence of choices, as in the "select a permutation; if it isn't a derangement, start over" procedure. Second, allow non-uniform choices. Third, allow uniform choices from larger sets. -- Fred W. Helenius <fredh@ix.netcom.com>