Update: Like the saying goes: problems worthy of attack prove their worth by biting back. Immediately after I posted the scheme below I realized that it too fails to sample all the derangements. The decomposition of a derangement I give in the description of the algorithms is incorrect. For example, it does not describe the derangement 1,2,3,0 of 0,1,2,3. The moral of the story: do the math before doing the coding :) . I am beginning to see why my (admittedly very superficial) online searches for a derangement sampling algorithm turned up nothing cleverer than a rejection method.

OK, below I give a first pass at a function to generate a random derangement. I think it samples all derangements fairly, but I have not verified this:

my @cols = 0..11;
randomly_derange( \@cols );
@nums = map [ @{$_}[@cols] ], @nums;

sub randomly_derange {
  my $arr = shift();
  my @i = 0..$#$arr;
  while ( @i ) {
    my @swap = map splice( @i, rand( @i ), 1 ), 1, 2;
    @{ $arr }[ @swap ] = @{ $arr }[ @swap[ 1, 0 ] ];
    last if @i == 3;
  }
  if ( @i ) {
    my @j = rand() < 0.5 ? @i[ 1, 2, 0 ] : @i[ 2, 0, 1 ];
    @{ $arr }[ @i ] = @{ $arr }[ @j ];
  }
}
[download]