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