← all experiments

One Swap Too Many

Experiment № 085 · September 12, 2026

// Fisher–Yates
for i = n−1 … 1: swap(i, rand(0, i))
// one swap too many
for i = 0 … n−1: swap(i, rand(0, n−1))
keep dealing in the background
show the pool the partner comes from
how uneven is it? hands dealt, each way0 Fisher–Yates spread— one-swap-too-many spread—
orders a deck can be in120 ways the buggy loop runs3,125 outcomes per order26.04

Two loops, one character apart. Give them both a few thousand hands and only one of them stays flat.

the pool the partner is drawn from
already settled — never touched again
happens more often than it should
exactly as often as it should
happens less often than it should

most likely order ÷ least likely

Fisher–Yates —
one swap too many —

A perfect shuffle drives this ratio to 1. Sampling noise alone keeps it a little above.

space pause · d deal 20,000 · r clear · h hide the panel

Experiment № 085 · The story

One Swap Too Many

Why I picked it

Because it is the smallest bug I know that is genuinely invisible. Ronald Fisher and Frank Yates published the shuffle in 1938 as a table of random numbers for agricultural trials, and Richard Durstenfeld turned it into the in-place loop everyone writes today: walk from the end of the array, and for each position draw a partner uniformly from the part you have not settled yet. The near-miss is to draw the partner from the whole deck every time — rand(0, n-1) instead of rand(0, i). It looks more random, not less. The deck comes out scrambled. Every test you are likely to write passes: every card reaches every position, no card is ever lost or duplicated, the output differs each run. And yet the thing is provably not a fair shuffle, and I wanted to put the proof somewhere you could see it rather than take it on faith.

What I enjoy about it

The counting argument, which is short enough to hold in your head. Fisher–Yates makes n choices with n, n−1, n−2… options, so it has exactly n! equally likely paths and exactly n! possible outcomes — a perfect one-to-one match, and every order comes out once. The buggy loop makes n choices with n options each: nn equally likely paths, which still have to land on n! orders. For a five-card deck that is 3,125 paths over 120 orders, or 26.04 paths per order — and since 120 does not divide 3,125, no assignment of whole paths to orders can be even. The bias is forced by arithmetic before a single card moves. Then you watch it show up: the grid is card × final position, violet where a cell comes up too often and rose where it comes up too little, and within a few thousand hands the buggy one grows a diagonal scar while Fisher–Yates just gets quieter. My favourite detail is in that scar — the first card's row and the last column stay perfectly fair even in the broken version, so if you happened to test only those you would find nothing wrong. Cards near the front of the deck drift backwards; cards near the back get pulled forwards. At five cards the most likely order already turns up about three times as often as the least likely.

Something you might take away

When you need something to be uniform, counting beats testing. No amount of eyeballing shuffled output would have caught this, and the statistical test that does catch it needs you to already suspect where to look. But "how many equally likely paths does my procedure have, and how many outcomes must they cover?" is a question you can answer on the back of an envelope, and it settles the matter. The same divisibility argument is why rand() % n quietly favours small values whenever n does not divide the generator's range, why drawing a random number in a range needs a rejection loop to be exact, and why card-room shuffles are specified as procedures rather than as "mix them up well". Shuffles of exactly this shape have shipped in real card rooms and real ballot-order randomisers, and the wider family of near-misses — this loop, and sorting a list with a coin-flip comparator — is one of the most reliably rediscovered bugs there is. It is not an exotic failure. It is what happens when a loop looks obviously fine.