How do you shuffle a deck so every one of the 52! orderings is equally likely? The obvious way — swap each card with a random one — is subtly biased and produces some orders more often than others. Fisher–Yates does it right, in one pass. And it is the dart where two things this campaign added to I-13 meet: the array and the seeded PRNG.
THE TECHNIQUE walk down, swap with an earlier-or-self slot
From the last position down to the second: pick a random index between 0 and i (inclusive), and swap. The “0 to i” is the whole secret — a naive “0 to n−1” swap looks the same and is provably biased. Shuffle, and check the counts stay flat. live demo
HISTORY & CREDIT from a 1938 table to every card game online
People call the naive “swap-with-anything” loop a shuffle; it is uniform only if you get the range exactly right. cited
1938 · Ronald Fisher & Frank Yates, in Statistical Tables, give the method as a pencil-and-paper randomization procedure. 1964 · Richard Durstenfeld recasts it as the modern in-place O(n) algorithm — the version everyone codes. the trap · picking the swap partner from 0..n−1 every step gives nⁿ equally-likely runs, which cannot divide evenly into n! orderings — so some permutations are over-represented. Fisher–Yates picks from 0..i, giving exactly n! equal outcomes. Knuth · presents it as Algorithm P (shuffle) in TAOCP, which fixed the name in programmers’ minds.
A one-character difference in the random range is the line between fair and rigged. exact
RECOMMEND FOR I-13 two additions meet — array × PRNG
The shuffle needs an array (to swap in place) and randomness (to choose partners). I-13 gained the first this turn and the second (the stdlib LCG) before — so it runs, and the permutation is valid (the sum of 0..7 stays 28 no matter the order):
def shuffle(I a, I i, I seed) {
if i <= 0 { -> a }
I r <- lcg(seed)
I j <- r % (i + 1) // 0..i -- the fair range
-> shuffle(swap(a, i, j), i - 1, r)
}
$ i13 run fisher.i13 # array + std/rng_lcg
sum = 28 # a real permutation of 0..7 (0+1+...+7 = 28), reordered
Recommend:nothing new — this is the campaign’s cleanest convergence. Two independent recommendations, integrated one at a time (the seeded PRNG as a library; the array as a value kind), meet in a single algorithm that now runs. The seed threads as a parameter (determinism kept in the open); the array threads as the return value. The loop, compounding: darts asked for random (004/030) and for aggregates (017/028); both landed; Fisher–Yates is where they shake hands.