note blokhead Here's the approach I wanted to code up, but I've been sufficiently distracted. <p> The number of derangements is <c>d(n) = (n-1)( d(n-1) + d(n-2) )</c>, and there is a combinatorial proof of this at [wp://Derangement|the wikipedia article]. That is, there are (n-1) ways to build an n-derangement out of a (n-1)-derangement, and (n-1) ways to build an n-derangement out of a (n-2)-derangment. Furthermore, these correspond uniquely to <i>all the ways</i> to build an n-derangement. <p> So here is a way to randomly generate an n-derangement: <ul> <li> Recursively generate either a (n-1)-derangement or (n-2)-derangement, with probabilities relative to d(n-1) and d(n-2). The base cases are d(1)=0 (no ways to generate a 1-derangement) and d(2)=1 (only 1 choice for a 2-derangement).</li> <li> Randomly pick one of the (n-1) ways to generate an n-derangement from the one you have, according to the combinatorial proof.</li> </ul> Unfortunately, I don't have any time to code this up, and the combinatorial proof is not written well. For the case of making an n-derangement out of an (n-1)-derangement, you simply add n to the end, and then swap the last position and a randomly chosen other position. I couldn't quite understand exactly what the wikipedia article was getting at for the other case, though, and it's been too long since I've thought of such things. <p> Maybe some curious monk can work this into usable code. But this approach is basically recursive: take a random starting derangement and choose a random way to augment it into a larger one. The end result will certainly be randomly distributed, provided you handle the (n-1) and (n-2) cases with the appropriate relative probabilities.. <p> All I managed to get into code was a simple routine to count d(n). It uses a different combinatorial identity that is more amenable to simple computation. It seems like you'd need this to get the relative probabilities for the (n-1) and (n-2) cases to work out: <c> sub num_d { my (\$n) = @_; return 1-\$n if \$n < 2; my \$d = 0; \$d += (-1)**\$_ + (\$_-1)*\$d for 2 .. \$n; return \$d; } </c> <!-- Node text goes above. Div tags should contain sig only --> <div class="pmsig"><div class="pmsig-137386"> <p> blokhead </div></div> 695750 695750