Recipe 4.18 Randomizing an Array

4.18.1 Problem

You want to randomly shuffle the elements of an array. 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 treat elements of an array in a random order.

4.18.2 Solution

Use the shuffle function from the standard List::Util module, which returns the elements of its input list in a random order.

```use List::Util qw(shuffle);
@array = shuffle(@array);```

4.18.3 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 three-element list. We generate three random numbers, each of which can have three possible values, yielding 27 possible outcomes. There are only six permutations of the three-element list, though. Because 27 isn't evenly divisible by 6, some outcomes are more likely than others.

The List::Util module's shuffle function avoids this bias to produce a more randomly shuffled result.

If all you want to do is pick one random element from the array, use:

`\$value = \$array[ int(rand(@array)) ];`

The rand function in perlfunc(1) and Chapter 29 of Programming Perl; for more on random numbers, see Recipe 2.6, Recipe 2.7, and Recipe 2.8; Recipe 4.20 provides another way to select a random permutation  Chapter 1. Strings  Chapter 2. Numbers  Chapter 3. Dates and Times  Chapter 4. Arrays  Introduction  Recipe 4.1 Specifying a List in Your Program  Recipe 4.2 Printing a List with Commas  Recipe 4.3 Changing Array Size  Recipe 4.4 Implementing a Sparse Array  Recipe 4.5 Iterating Over an Array  Recipe 4.6 Iterating Over an Array by Reference  Recipe 4.7 Extracting Unique Elements from a List  Recipe 4.8 Finding Elements in One Array but Not Another  Recipe 4.9 Computing Union, Intersection, or Difference of Unique Lists  Recipe 4.10 Appending One Array to Another  Recipe 4.11 Reversing an Array  Recipe 4.12 Processing Multiple Elements of an Array  Recipe 4.13 Finding the First List Element That Passes a Test  Recipe 4.14 Finding All Elements in an Array Matching Certain Criteria  Recipe 4.15 Sorting an Array Numerically  Recipe 4.16 Sorting a List by Computable Field  Recipe 4.17 Implementing a Circular List  Recipe 4.18 Randomizing an Array  Recipe 4.19 Program: words  Recipe 4.20 Program: permute  Chapter 5. Hashes  Chapter 6. Pattern Matching  Chapter 7. File Access  Chapter 8. File Contents  Chapter 9. Directories  Chapter 10. Subroutines  Chapter 11. References and Records  Chapter 12. Packages, Libraries, and Modules  Chapter 13. Classes, Objects, and Ties  Chapter 14. Database Access  Chapter 15. Interactivity  Chapter 16. Process Management and Communication  Chapter 17. Sockets  Chapter 18. Internet Services  Chapter 19. CGI Programming  Chapter 20. Web Automation  Chapter 21. mod_perl  Chapter 22. XML