The simple, perfect algorithm that ensures every possible shuffle is equally likely to occur.
In short: Shuffling a list seems trivial, but most intuitive methods introduce subtle biases. The Fisher-Yates shuffle is the gold standard for generating an unbiased permutation. By swapping elements in place, it achieves optimal efficiency, ensuring every possible arrangement has an identical mathematical probability of appearing. It is a masterpiece of algorithmic elegance.
Originally published in 1938 by Ronald Fisher and Frank Yates, the algorithm was designed for pencil-and-paper use in statistical research. It required a table of random numbers to strike out elements from a list, moving them to a new sequence. While mathematically sound, this manual process was cumbersome for computers, which struggled with the overhead of tracking and counting remaining items.
In 1964, Richard Durstenfeld introduced a modern, in-place version that revolutionized the process for digital systems. Instead of striking out items, Durstenfeld’s method swaps the chosen element with the last unstruck item in the array. This optimization reduced the time complexity to linear time, making it the standard approach popularized by Donald E. Knuth in his seminal work, The Art of Computer Programming.
The algorithm’s reliability depends entirely on the quality of the random number source. A common pitfall is the accidental implementation of Sattolo’s algorithm, published in 1986. While similar to the Fisher-Yates shuffle, Sattolo’s variant generates only cyclic permutations of length n. If a programmer mistakenly uses this for a general shuffle, they restrict the output to a small subset of possible outcomes, introducing a significant bias that undermines the goal of true randomness.
Today, the Fisher-Yates shuffle remains the optimal choice for shuffling. It is not only efficient but also flexible; it can be stopped halfway or generated incrementally if only a partial permutation is needed. Recent advancements have even adapted the logic for parallel computing, with researchers like Shun, Gu, Blelloch, Fineman, and Gibbons demonstrating how to parallelize the process while maintaining its linear work and unbiased results.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Fisher–Yates shuffle
To cite this card, link to https://intellectplus.co.uk/app/science-fisher-yates-shuffle.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Basics · More in Science · Latest · A–Z · All topics