
Jasmine
Administrator
Jan 19, 2001, 3:15 PM
Post #1 of 1
(1014 views)
|
|
How do I shuffle an array randomly?
|
Can't Post
|
|
(From the Perl FAQ) How do I shuffle an array randomly? Use this: # fisher_yates_shuffle( \@array ) : # generate a random permutation of @array in place sub fisher_yates_shuffle { my $array = shift; my $i; for ($i = @$array; --$i; ) { my $j = int rand ($i+1); next if $i == $j; @$array[$i,$j] = @$array[$j,$i]; } } fisher_yates_shuffle( \@array ); # permutes @array in place You've probably seen shuffling algorithms that works using splice, randomly picking another element to swap the current element with: srand; @new = (); @old = 1 .. 10; # just a demo while (@old) { push(@new, splice(@old, rand @old, 1)); } This is bad because splice is already O(N), and since you do it N times, you just invented a quadratic algorithm; that is, O(N**2). This does not scale, although Perl is so efficient that you probably won't notice this until you have rather largish arrays.
|