## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

# Randomizing an Array

## Problem

You 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.

## Solution

Swap 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 ) ];```

## Discussion

Shuffling 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 Also

The `rand` function in ```perlfunc ```(1) and Chapter 3 of Programming Perl ; for more on random numbers, see Section 2.7, Section 2.8, and Section 2.9; Section 4.19 provides another way to select a random permutation

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required