Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

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 );
where
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


Comment on Re: swap columns in a 2-dim array
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://467623]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (6)
As of 2015-07-05 23:58 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (68 votes), past polls