4.17. Randomizing an ArrayProblemYou want to shuffle the elements of an array randomly. The obvious application is writing a card game, where you must shuffle a deck of cards, but it is equally applicable to any situation where you want to deal with elements of an array in a random order. SolutionSwap each element in the array with another randomly selected, element: # 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 Or, pick a random permutation using the code in Example 4.4 : $permutations = factorial( scalar @array ); @shuffle = @array [ n2perm( 1+int(rand $permutations), $#array ) ]; DiscussionShuffling is a surprisingly tricky process. It's easy to write a bad shuffle: sub naive_shuffle { # don't do this for (my $i = 0; $i < @_; $i++) { my $j = int rand @_; # pick random element ($_[$i], $_[$j]) = ($_[$j], $_[$i]); # swap 'em } } This algorithm is biased; the list's possible permutations don't all have the same probability of being generated. The proof of this is simple: take the case where we're passed a 3element list. We generate three random numbers, each of which can have three possible values, yielding 27 possible outcomes here. There are only 6 permutations of the 3element list, though. Because 27 isn't evenly divisible by 6, some outcomes are more likely than others. The FisherYates shuffle avoids this bias by changing the range of the random numbers it selects. See Also
The
Copyright © 2002 O'Reilly & Associates. All rights reserved. 
