The Fisher–Yates shuffle is a randomized algorithm for rearranging a finite sequence into a random order. Given distinguishable elements, it produces each of the possible permutations with equal probability, provided that its random choices are unbiased and appropriately independent. Its modern implementation repeatedly swaps an element with a randomly chosen element from the portion not yet finalized, taking linear time and constant auxiliary space.
History
Ronald A. Fisher and Frank Yates described the original method in their 1938 book Statistical Tables for Biological, Agricultural and Medical Research. It was intended for use with tables of random numbers: repeatedly select an item uniformly from those remaining, record it, and remove it from further consideration.
Richard Durstenfeld published a computer-oriented version in 1964. Instead of removing an item and shifting the remaining elements, this version exchanges the selected item with an element at the boundary of the unprocessed region. Donald Knuth subsequently presented the algorithm in The Art of Computer Programming, helping establish its widespread use.
“Fisher–Yates shuffle” commonly refers to this modern, in-place version. The names “Durstenfeld shuffle” and “Knuth shuffle” also occur, although the historical contributions are distinct.
Modern algorithm
For a zero-indexed array of length , the algorithm proceeds from the last position toward the first. At position , it chooses an integer uniformly from the inclusive range through , then swaps and .
In pseudocode:
fisher_yates(A):
n = length(A)
for i = n - 1 down to 1:
j = uniform_integer(0, i)
swap(A[i], A[j])
Here, uniform_integer(0, i) must include both endpoints. Choosing , and therefore leaving the current element in place, is a necessary part of the algorithm.
After each iteration, position contains its final element. Later iterations operate only on positions below it. Arrays of length zero or one require no swaps.
An equivalent forward version visits , choosing uniformly from . Both forms work by selecting uniformly from the remaining elements and shrinking the unprocessed region.
Why the result is uniform
The correctness argument can be expressed as a loop invariant: before each selection, the unprocessed region contains exactly the elements not yet assigned to finalized positions.
Consider any particular target arrangement of distinct elements:
- Its required last element is selected with probability .
- Conditional on that selection, its required next-to-last element is selected with probability .
- This continues until the last remaining element is determined.
Thus the probability of obtaining that target arrangement is
Because this holds for every permutation, the output has a uniform probability distribution over all permutations.
Equivalently, the sequence of random index choices has
possible outcomes. Each choice sequence corresponds to exactly one output permutation, and every choice sequence has the same probability.
Repeated values
The proof treats input elements as distinguishable objects. If several elements have the same visible value, their identities can still be regarded as distinct during the shuffle.
For multiplicities , each distinct visible arrangement corresponds to labeled permutations. Consequently, every distinct visible arrangement also has equal probability:
Repeated values therefore do not invalidate the uniformity guarantee.
Computational cost
The modern algorithm performs iterations and at most swaps. Assuming constant-time random array access, swapping, and bounded-integer generation, its time complexity is , and its auxiliary space complexity is .
These assumptions matter:
- A linked list does not generally support constant-time access by index, so directly applying the array implementation can take quadratic time.
- The original selection-and-removal method can take time when each removal shifts the remaining array elements.
- Swapping large records may cost more than swapping fixed-size values or references.
- Producing unbiased bounded integers has its own computational and randomness costs.
The shuffle is therefore described as linear-time primarily in the usual array-based model of computational complexity.
Random-number generation and implementation pitfalls
The mathematical algorithm is unbiased, but an implementation inherits limitations from its random-number source and its method of generating bounded integers.
Modulo bias
Suppose a random integer is uniform over . Computing
does not generally produce a uniform integer in . It is uniform only when divides ; otherwise, some remainders occur more frequently than others.
A standard remedy is rejection sampling. Define
Draw repeatedly until , then return . The accepted range contains an equal number of representatives of every remainder. This construction assumes ; larger bounds require a larger random range or another method.
Floating-point scaling
Computing is mathematically correct if is an ideal continuous uniform random variable on . Actual computer generators produce values from a finite set, so scaling can introduce bias or make some indices unreachable, especially for large bounds. Rounding instead of taking the floor can introduce additional errors.
Pseudorandom generators and seeds
Most implementations use a pseudorandom number generator. A fixed seed produces a deterministic sequence and, with a fixed implementation, a repeatable shuffle.
Uniformity of the abstract algorithm does not establish that a particular generator can reach every permutation. If the generator has only possible initial states, a deterministic shuffle driven solely by those states can produce at most distinct outputs. Thus is necessary, but not sufficient, for all permutations to be reachable.
Likewise, individually uniform index choices are not enough if correlations between successive choices change their joint distribution. The proof requires each selection to be uniform conditional on the preceding choices.
For applications involving cryptography or adversarial prediction, uniformity and unpredictability are separate requirements. Fisher–Yates does not make a predictable random source secure, and it does not by itself establish the fairness of a larger protocol.
Incorrect index ranges
A common incorrect approach swaps each position with a random position anywhere in the full array. Earlier placements can then be disturbed, and the resulting permutation is generally biased.
For example, an implementation that makes three independent choices among all three positions has equally likely choice sequences. These cannot be divided equally among the permutations.
Excluding the current position is also incorrect for an ordinary Fisher–Yates shuffle. It prevents some outputs, including the unchanged arrangement for two elements.
Variants and related algorithms
Inside-out shuffle
The inside-out variant constructs a shuffled output array while processing the input from left to right:
inside_out(input):
allocate output with length(input) positions
for i = 0 to length(input) - 1:
j = uniform_integer(0, i)
if j != i:
output[i] = output[j]
output[j] = input[i]
return output
At each step, the new element is inserted into a uniformly selected position, and any displaced element moves to the newly created position. This produces a uniform permutation without modifying the input, but requires output space.
Partial shuffle and sampling
When only randomly selected elements are required, a forward Fisher–Yates shuffle can stop after finalizing its first positions. Those positions form a uniformly random ordered sample without replacement. Ignoring their order gives a uniformly random -element subset.
With a mutable, random-access input array, this requires swaps. For streams or inputs whose size is not known in advance, reservoir sampling addresses a different access model.
Sattolo’s algorithm
Sattolo’s algorithm resembles the backward shuffle but chooses from , excluding . It generates permutations consisting of a single cycle rather than all permutations.
It is not a general-purpose substitute for Fisher–Yates. For more than one element, a single-cycle permutation has no fixed points, but not every fixed-point-free permutation consists of one cycle.
Random-key sorting
Another approach assigns random keys to elements and applies a sorting algorithm. With independent continuous keys and no ties, the resulting order is uniform. Finite keys introduce ties whose handling can affect the distribution, and comparison sorting generally takes time.
Using a comparator that returns random comparison results is different from sorting by fixed random keys. Such a comparator need not define a consistent ordering and can violate the sorting routine’s requirements.
Applications and testing
Fisher–Yates is used for virtual card decks, randomized experimental orders, simulation inputs, and the reordering of training data in machine learning. Its guarantee concerns the order of the supplied elements; it does not ensure that those elements were collected or selected without bias.
Tests can check that the output preserves the input’s elements and multiplicities, handles boundary cases, and behaves reproducibly under a fixed generator configuration. For very small arrays, enumerating all possible index-choice sequences can verify that every permutation occurs equally often.
Statistical tests can detect some implementation errors, but equal frequencies for individual element positions do not prove that complete permutations are uniform. Correlations between positions may remain even when every element appears equally often in every position.