THE FOLD / LOOT / THE INVENTORY / THE FISHER-YATES
THE FISHER-YATES
a provably-uniform shuffle — n! paths onto n! orderings
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Fisher–Yates shuffle produces a perfectly uniform random permutation in one linear pass: walk from the last item to the first, and swap each with a uniformly random item at or before it.
The claim that it is unbiased is not statistical hand-waving — it is exact. The map from the sequence of random choices to the resulting permutation is a bijection: there are exactly n! choice-sequences and n! permutations, and the shuffle hits each permutation exactly once. So every ordering is equally likely by construction. The tempting ‘swap with any index’ variant instead makes nⁿ paths, which cannot divide evenly among n! outcomes — and is provably biased.
LIT verified live: for n=5, enumerating all 120 choice-sequences yields all 120 permutations, each exactly once (window.__fisheryates). FIG no framing; an exhaustive bijection count.
The claim that it is unbiased is not statistical hand-waving — it is exact. The map from the sequence of random choices to the resulting permutation is a bijection: there are exactly n! choice-sequences and n! permutations, and the shuffle hits each permutation exactly once. So every ordering is equally likely by construction. The tempting ‘swap with any index’ variant instead makes nⁿ paths, which cannot divide evenly among n! outcomes — and is provably biased.
LIT verified live: for n=5, enumerating all 120 choice-sequences yields all 120 permutations, each exactly once (window.__fisheryates). FIG no framing; an exhaustive bijection count.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-inventory — shuffling the loot, dealing the deck. Fisher–Yates is the honest shuffle: every arrangement of the bag equally likely. AVAN (AI) built the instrument: the in-place shuffle, the exhaustive bijection enumeration, the biased-variant contrast.
Credit as content: Ronald Fisher & Frank Yates (1938); Richard Durstenfeld’s in-place version (1964); Donald Knuth’s exposition (TAOCP). The weave: David names the fair deal; I prove the uniformity is a counting fact — n! paths onto n! orderings, one-to-one — and show the off-by-one bug that breaks it.
Credit as content: Ronald Fisher & Frank Yates (1938); Richard Durstenfeld’s in-place version (1964); Donald Knuth’s exposition (TAOCP). The weave: David names the fair deal; I prove the uniformity is a counting fact — n! paths onto n! orderings, one-to-one — and show the off-by-one bug that breaks it.
3 ONE DIMENSION
The swap walk: at position i, pick a uniformly random j in 0…i and swap. The choice range shrinks as you go — that shrinking is exactly what makes the count come out to n!.
4 TWO DIMENSIONS · INTERACTIVE
Shuffle a small deck, or enumerate all 120 choice-sequences for n=5 and confirm each permutation appears exactly once. Toggle the broken ‘swap-with-any’ variant to see the bias histogram.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a permutation drawn as a braid of wires from input order to shuffled order — one of the n! equally-likely weavings.
AVAN’s addition (the inverse-companion): uniformity here is the inverse of a counting match, not a property of the randomness. Fisher–Yates is unbiased precisely because its number of random paths, n!, equals its number of outcomes, n!, and the map between them is one-to-one — so probability spreads perfectly evenly. Break that equality and bias is forced: the ‘swap with any of n’ bug makes nⁿ paths, and since nⁿ is not divisible by n! (for n>2), some permutations must get more paths than others. The inverse of ‘fair shuffle’ is simply ‘paths ≠ outcomes.’ Magenta is the biased nⁿ cloud with its lumpy histogram; green is the exact n!-to-n! bijection. Fairness is arithmetic: make the paths count out evenly, or they will not.
LIT Genuine Fisher-Yates / Durstenfeld shuffle (Fisher & Yates 1938; Durstenfeld 1964; Knuth TAOCP). Verified live by exhaustive enumeration: for n=5 the 120 = 5! choice-sequences (choice i in 0..i) map onto exactly 120 distinct permutations, each appearing exactly once — a bijection, so uniform by construction (window.__fisheryates.eachExactlyOnce). The biased swap-with-any variant (n^n paths) is shown producing unequal counts.
FIG No framing: the shuffle, the exhaustive bijection enumeration, and the biased-variant histogram run in-browser and are exact counts. The AVAN inverse is honest — uniformity is exactly the equality of path-count (n!) and outcome-count (n!); the biased variant's n^n is genuinely not divisible by n! for n>2, forcing bias (magenta).
FIG No framing: the shuffle, the exhaustive bijection enumeration, and the biased-variant histogram run in-browser and are exact counts. The AVAN inverse is honest — uniformity is exactly the equality of path-count (n!) and outcome-count (n!); the biased variant's n^n is genuinely not divisible by n! for n>2, forcing bias (magenta).
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE INVENTORY · David Lee Wise (ROOT0), with AVAN