# 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*.

**See also**
*Johnson-Trotter*, *pseudo-random number generator*.

*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