You can easily modify your shuffling procedure to give you a shuffle in which no position remains fixed (this is called a derangement):
With this change, then all you need to shuffle the columns is this:sub fys { my $arr = shift; my $i = @{ $arr }; while ( $i ) { my $j = int rand $i; @$arr[$i,$j] = @$arr[$j,$i]; --$i; } }
@nums = map [ @{$_}[@cols] ], @nums;
The problem with this simple solution is that it cannot generate all possible derangements. For example, the modified FY misses the derangment 1,0,3,2 of 0,1,2,3.
I looked online for algorithms to fairly sample the space of all derangments of an input list, and the best I found was based on using the standard FY until a derangement is found (i.e. a rejection method). If you need to randomly sample from the space of all possible derangements of the columns, then keep your original FY procedure, but modify the creation of @cols to this:
wheremy @cols = 0..11; do { fys( \@cols ); } until is_deranged( \@cols );
The probability of getting a derangement from a random sample of permutations is ≈ 1/e (i.e. about three trials required per derangement, on average). Moreover, one can optimize the FY procedure around this problem (by having it automatically restart when it encounters a "trivial" swap, i.e. $i == $j), which obviates the need to have a specific rejection step. Therefore this approach has essentially the same time and space growth properties as FY.sub is_deranged { my $arr = shift; $arr->[ $_ ] == $_ and return for 0..$#$arr; return 1; }
Update: Added the stuff about fair sampling, and the rejection method for obtaining a random derangement.
the lowliest monk
In reply to Re: swap columns in a 2-dim array
by tlm
in thread swap columns in a 2-dim array
by davidj
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |