The Fisher–Yates shuffle, named after Ronald Fisher and Frank Yates, also known as the Knuth shuffle, after Donald Knuth, is an algorithm for generating a random permutation of a finite set—in plain terms, for randomly shuffling the set.
Unbiased
Properly implemented, the Fisher–Yates shuffle is unbiased, so that every permutation is equally likely. The modern version of the algorithm is also rather efficient, requiring only time proportional to the number of items being shuffled and no additional storage space.
The process
The basic process of Fisher–Yates shuffling is similar to randomly picking numbered tickets out of a hat, or cards from a deck, one after another until there are no more left. What the specific algorithm provides is a way of doing this numerically in an efficient and rigorous manner that, properly done, guarantees an unbiased result.
The original Fisher and Yates' method
Their method was designed to be implemented using pencil and paper, with a precomputed table of random numbers as the source of randomness.
The basic method given for generating a random permutation of the numbers 1–N goes as follows: in their book The Fisher–Yates shuffle, in its original form, was described in 1938 by Ronald A. Fisher and Frank Yates; Statistical tables for biological, agricultural and medical research. (Later editions describe a somewhat different method attributed to C. R. Rao.)
- Write down the numbers from one to N.
- Pick a random number k between one and the number of unstruck numbers remaining (inclusive).
- Counting from the low end, strike out the kth number not yet struck out, and write it down elsewhere.
- Repeat from step 2 until all the numbers have been struck out.
- The sequence of numbers written down in step 3 is now a random permutation of the original numbers.
Provided that the random numbers picked in step 2 above are truly random and unbiased, so will the resulting permutation be. Fisher and Yates took care to describe how to obtain such random numbers in any desired range from the supplied tables in a manner which avoids any bias.
They also suggested the possibility of using a simpler method — picking random numbers from one to N and discarding any duplicates—to generate the first half of the permutation, and only applying the more complex algorithm to the remaining half, where picking a duplicate number would otherwise become frustratingly common.
Posts
