Here's the approach I wanted to code up, but I've been sufficiently distracted.
The number of derangements is d(n) = (n1)( d(n1) + d(n2) ), and there is a combinatorial proof of this at the wikipedia article. That is, there are (n1) ways to build an nderangement out of a (n1)derangement, and (n1) ways to build an nderangement out of a (n2)derangment. Furthermore, these correspond uniquely to all the ways to build an nderangement.
So here is a way to randomly generate an nderangement:
 Recursively generate either a (n1)derangement or (n2)derangement, with probabilities relative to d(n1) and d(n2). The base cases are d(1)=0 (no ways to generate a 1derangement) and d(2)=1 (only 1 choice for a 2derangement).
 Randomly pick one of the (n1) ways to generate an nderangement from the one you have, according to the combinatorial proof.
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 nderangement out of an (n1)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.
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 (n1) and (n2) cases with the appropriate relative probabilities..
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 (n1) and (n2) cases to work out:
sub num_d {
my ($n) = @_;
return 1$n if $n < 2;
my $d = 0;
$d += (1)**$_ + ($_1)*$d for 2 .. $n;
return $d;
}
Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
Read Where should I post X? if you're not absolutely sure you're posting in the right place.
Please read these before you post! —
Posts may use any of the Perl Monks Approved HTML tags:
 a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

For: 

Use: 
 &   & 
 <   < 
 >   > 
 [   [ 
 ]   ] 
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.

