The Fisher-Yates shuffle is an algorithm for generating a random permutation of a list of 
distinct elements. Starting with the elements 
, 
, ..., 
, successively take 
, 
, ..., 2. At each step, choose 
uniformly at random from 1, 2, ..., 
and exchange 
with 
. An equivalent version proceeds from left to right, exchanging
with an element chosen uniformly from positions 
through 
.
There are 
choices at step 
,
and every permutation corresponds to exactly one
sequence of choices. Provided the choices are statistically independent
and each has a uniform distribution, every
permutation therefore has probability
 |
With a random-access array and constant-time generation of each random index, the algorithm runs in 
time and uses 
auxiliary space in big-O notation (Durstenfeld
1964, Knuth 1998, Eberl 2016).
Uniform selection of 
from its stated range is essential. Reducing an integer-valued
random quantity modulo a modulus 
introduces bias unless its residue
classes are equally likely, as does exchanging each element with an element chosen
from the entire list at every step. The latter procedure is known as the exchange
shuffle and does not in general produce a uniform random permutation.
The original procedure was introduced by Fisher and Yates (1938). The efficient in-place version above is due to Durstenfeld (1964). It is also known as the Knuth shuffle after Donald Knuth (Knuth 1998).
