# 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). 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 E. Black.

Entry modified 23 May 2011.

HTML page formatted Tue Dec 6 16:16:32 2011.

Cite this as:

Paul E. Black, "Fisher-Yates shuffle", in
*Dictionary of Algorithms and Data
Structures* [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 23 May 2011. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/fisherYatesShuffle.html