The Fisher–Yates shuffle is an algorithm for shuffling a finite sequence. The algorithm takes a list of all the elements of the sequence, and continually determines the next element in the shuffled sequence by randomly drawing an element from the list until no elements remain. The algorithm produces an unbiased permutation: every permutation is equally likely. The modern version of the algorithm takes time proportional to the number of items being shuffled and shuffles them in place.
The Fisher–Yates shuffle is named after Ronald Fisher and Frank Yates, who first described it. It is also known as the Knuth shuffle after Donald Knuth. A variant of the Fisher–Yates shuffle, known as Sattolo's algorithm, may be used to generate random cyclic permutations of length n instead of random permutations.
Fisher and Yates' original method
The original Fisher–Yates shuffle was published in 1938 by Ronald Fisher and Frank Yates in their book Statistical tables for biological, agricultural and medical research. Note: the 6th edition, , is available on the web, but gives a different shuffling algorithm by C. R. Rao. Their description of the algorithm used pencil and paper; a table of random numbers provided the randomness. The basic method given for generating a random permutation of the numbers 1 through N goes as follows:
Write down the numbers from 1 through N. Pick a random number k between one and the number of unstruck numbers remaining (inclusive). Counting from the low end, strike out the kth number not yet struck out, and write it down at the end of a separate list. Repeat from step 2 until all the numbers have been struck out. The sequence of numbers written down in step 3 is now a random permutation of the original numbers.
Provided that the random numbers picked in step 2 above are truly random and unbiased, so will be the resulting permutation. Fisher and Yates took care to describe how to obtain such random numbers in any desired range from the supplied tables in a manner which avoids any bias. They also suggested the possibility of using a simpler method — picking random numbers from one to N and discarding any duplicates—to generate the first half of the permutation, and only applying the more complex algorithm to the remaining half, where picking a duplicate number would otherwise become frustratingly common.
The modern algorithm The modern version of the Fisher–Yates shuffle, designed for computer use, was introduced by Richard Durstenfeld in 1964 and popularized by Donald E. Knuth in The Art of Computer Programming as "Algorithm P (Shuffling)". Neither Durstenfeld's article nor Knuth's first edition of The Art of Computer Programming acknowledged the work of Fisher and Yates. Subsequent editions of Knuth's The Art of Computer Programming mention Fisher and Yates' contribution.
The algorithm described by Durstenfeld is more efficient than that given by Fisher and Yates: whereas a naïve computer implementation of Fisher and Yates' method would spend needless time counting the remaining numbers in step 3 above, Durstenfeld's solution is to move the "struck" numbers to the end of the list by swapping them with the last unstruck number at each iteration. This reduces the algorithm's time complexity to compared to for the naïve implementation. This change gives the following algorithm (for a zero-based array).
-- To shuffle an array a of n elements (indices 0..n − 1): for i from n − 1 down to 1 do j ← random integer such that 0 ≤ j ≤ i exchange a[j] and a[i]
An equivalent version which shuffles the array in the opposite direction (from lowest index to highest) is: for i from 0 to n − 2 do j ← random integer such that i ≤ j ≤ n − 1 exchange a[i] and a[j]
Since the inverse of a uniformly random permutation is uniformly random, one can equally well perform the loops above in the other direction: for i from 1 to n − 1 do j ← random integer such that 0 ≤ j ≤ i exchange a[j] and a[i]
Or: for i from n − 2 down to 0 do j ← random integer such that i ≤ j ≤ n − 1 exchange a[i] and a[j]
Examples
Pencil-and-paper method
This example permutes the letters from A to H using Fisher and Yates' original method, starting with the letters in alphabetical order:
Range Roll Scratch Result A B C D E F G H
A random number j from 1 to 8 is selected. If j=3, for example, then one strikes out the third letter on the scratch pad and writes it down as the result:
Range Roll Scratch Result 1–8 3 A B D E F G H C
A second random number is chosen, this time from 1 to 7. If the number is 4, then one strikes out the fourth letter not yet struck off the scratch pad and adds it to the result:
Range Roll Scratch Result 1–7 4 A B D F G H C E
The next random number is selected from 1 to 6, and then from 1 to 5, and so on, always repeating the strike-out process as above:
Range Roll Scratch Result 1–6 5 A B D F H C E G 1–5 3 A B F H C E G D 1–4 4 A B F C E G D H 1–3 1 B F C E G D H A 1–2 2 B C E G D H A F C E G D H A F B
Modern method
In Durstenfeld's version of the algorithm, instead of striking out the chosen letters and copying them elsewhere, they are swapped with the last letter not yet chosen. Starting with the letters from A to H as before:
Range Roll Scratch Result A B C D E F G H
Select a random number j from 1 to 8, and then swap the jth and 8th letters. So, if the random number is 6, for example, swap the 6th and 8th letters in the list:
Range Roll Scratch Result 1–8 6 A B C D E H G F
The next random number is selected from 1 to 7, and the selected letter is swapped with the 7th letter. If it is 2, for example, swap the 2nd and 7th letters:
Range Roll Scratch Result 1–7 2 A G C D E H B F
The process is repeated until the permutation is complete:
Range Roll Scratch Result 1–6 6 A G C D E H B F 1–5 1 E G C D A H B F 1–4 3 E G D C A H B F 1–3 3 E G D C A H B F 1–2 1 G E D C A H B F
After eight steps, the algorithm is complete and the resulting permutation is G E D C A H B F.
Python implementation This example shows a simple Python implementation of the Fisher–Yates shuffle. import random
def shuffle(numbers: list[int]) -> list[int]: for i in range(len(numbers) - 1, 0, -1): j = random.randint(0, i) numbers[i], numbers[j] = numbers[j], numbers[i] return numbers
JavaScript implementation This example shows a simple JavaScript implementation of the Fisher–Yates shuffle. function shuffleArray(array) { for (let i = array.length - 1; i >= 1; i--) { const j = Math.floor(Math.random() * (i + 1)); [array[i], array[j]] = [array[j], array[i]];
return array; }
Variants
Forward variant
The algorithm is normally presented as building the shuffled result from right to left. However, it works equally well in the forward direction (think of inserting a new card into a random position in an already shuffled deck).
In the Python it is:
from random import randint
def shuffle(seq): for i in range(1, len(seq)): j = randint(0, i) seq[i], seq[j] = seq[j], seq[i]
Sattolo's algorithm + The six (3!) cyclic permutations of ABCD generated by Sattolo's algorithm Cyclicpermutation Example BCDA ABCD→DABC→CDAB→BCDA→ABCD... DABC ABCD→BCDA→CDAB→DABC→ABCD... BDAC ABCD→CADB→DCBA→BDAC→ABCD... CADB ABCD→BDAC→DCBA→CADB→ABCD... CDBA ABCD→DCAB→BADC→CDBA→ABCD... DCAB ABCD→CDBA→BADC→DCAB→ABCD...
A very similar algorithm was published in 1986 by Sandra Sattolo for generating uniformly distributed cycles of (maximal) length n. The only difference between Durstenfeld's and Sattolo's algorithms is that in the latter, in step 2 above, the random number j is chosen from the range between 1 and i − 1 (rather than between 1 and i) inclusive. This simple change modifies the algorithm so that the resulting permutation always consists of a single cycle.
In fact, as described below, it is quite easy to accidentally implement Sattolo's algorithm when the ordinary Fisher–Yates shuffle is intended. This will bias the results by causing the permutations to be picked from the smaller set of (n − 1)! cycles of length n, instead of from the full set of all n! possible permutations.
The fact that Sattolo's algorithm always produces a cycle of length n can be shown by induction. Assume by induction that after the initial iteration of the loop, the remaining iterations permute the first n − 1 elements according to a cycle of length n − 1 (those remaining iterations are just Sattolo's algorithm applied to those first n − 1 elements). This means that tracing the initial element to its new position p, then the element originally at position p to its new position, and so forth, one only gets back to the initial position after having visited all other positions. Suppose the initial iteration swapped the final element with the one at (non-final) position k, and that the subsequent permutation of first n − 1 elements then moved it to position l; we compare the permutation of all n elements with that remaining permutation σ of the first n − 1 elements. Tracing successive positions as just mentioned, there is no difference between and σ until arriving at position k. But then, under the element originally at position k is moved to the final position rather than to position l, and the element originally at the final position is moved to position l. From there on, the sequence of positions for again follows the sequence for σ, and all positions will have been visited before getting back to the initial position, as required.
As for the equal probability of the permutations, it suffices to observe that the modified algorithm involves (n − 1)! distinct possible sequences of random numbers produced, each of which clearly produces a different permutation, and each of which occurs—assuming the random number source is unbiased—with equal probability. The (n − 1)! different permutations so produced precisely exhaust the set of cycles of length n: each such cycle has a unique cycle notation with the value n in the final position, which allows for (n − 1)! permutations of the remaining values to fill the other positions of the cycle notation.
A sample implementation of Sattolo's algorithm in Python is:
from random import randrange
def sattolo_cycle(items) -> None: """Sattolo's algorithm.""" i = len(items) while i > 1: i = i - 1 j = randrange(i) # 0 <= j <= i-1 items[j], items[i] = items[i], items[j]
Parallel variants Several parallel shuffle algorithms, based on Fisher–Yates have been developed.
In 1990, Anderson developed a parallel version for machines with a small number of processors accessing shared memory. The algorithm generates random permutations uniformly so long as the hardware operates in a fair manner.
In 2015, Bacher et al. produced MERGESHUFFLE, an algorithm that divides the array into blocks of roughly equal size, uses Fisher–Yates to shuffle each block, and then uses a random merge recursively to give the shuffled array. Also in 2015, Shun, Gu, Blelloch, Fineman, and Gibbons showed how to directly parallelize the original Fisher-Yates shuffle to get a parallel algorithm with linear work and polylogarithmic depth.
Comparison with other shuffling algorithms
The asymptotic time and space complexity of the Fisher–Yates shuffle are optimal. Combined with a high-quality unbiased random number source, it is also guaranteed to produce unbiased results. Compared to some other solutions, it also has the advantage that, if only part of the resulting permutation is needed, it can be stopped halfway through, or even stopped and restarted repeatedly, generating the permutation incrementally as needed.
Naïve method