Fisher-Yates shuffle

(algorithm)

Definition: Randomly permute N elements by exchanging each element e_i with a random element from i to N. It consumes Θ(N log N) bits and runs in linear time.

Generalization (I am a kind of ...)
ideal random shuffle, permutation.

Note: The algorithm can be viewed as a reverse selection sort. It is described in some detail as algorithm 3.4.2P in [Knuth97, 2:145].

For even a rather small number of elements (or cards), the total number of permutations is far larger than the period of most pseudo-random number generators. This implies that most permutations will never be generated. (After documentation for random.shuffle() in Python, particularly v2.6.1.)

Author: PEB

Implementation

Ben Pfaff's answer to how can I shuffle the contents of an array? (C). Mike Bostock's animations with code (JavaScript). An implementation (Java) due to Sedgewick and Wayne (search for Shuffling).

More information

R. A. Fisher and F. Yates, Example 12, Statistical Tables, London, 1938.
Richard Durstenfeld, Algorithm 235: Random permutation, CACM 7(7):420, July 1964.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 9 March 2015.
HTML page formatted Mon Mar 9 13:46:10 2015.

Cite this as:
Paul E. Black, "Fisher-Yates shuffle", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 9 March 2015. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/fisherYatesShuffle.html