Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw

Re: swap columns in a 2-dim array

by tlm (Prior)
on Jun 17, 2005 at 08:59 UTC ( #467623=note: print w/replies, xml ) Need Help??

in reply to swap columns in a 2-dim array

You can easily modify your shuffling procedure to give you a shuffle in which no position remains fixed (this is called a derangement):

sub fys { my $arr = shift; my $i = @{ $arr }; while ( $i ) { my $j = int rand $i; @$arr[$i,$j] = @$arr[$j,$i]; --$i; } }
With this change, then all you need to shuffle the columns is this:
@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:

my @cols = 0..11; do { fys( \@cols ); } until is_deranged( \@cols );
sub is_deranged { my $arr = shift; $arr->[ $_ ] == $_ and return for 0..$#$arr; return 1; }
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.

Update: Added the stuff about fair sampling, and the rejection method for obtaining a random derangement.

the lowliest monk

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://467623]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (3)
As of 2017-04-26 09:37 GMT
Find Nodes?
    Voting Booth?
    I'm a fool:

    Results (471 votes). Check out past polls.