ЭЛЕКТРОННАЯ БИБЛИОТЕКА КОАПП |
Сборники Художественной, Технической, Справочной, Английской, Нормативной, Исторической, и др. литературы. |
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 3-element 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 3-element list, though. Because 27 isn't evenly divisible by 6, some outcomes are more likely than others. The Fisher-Yates shuffle avoids this bias by changing the range of the random numbers it selects. See AlsoThe |