Commissioned for this museum · after Fisher & Yates, 1938; Durstenfeld, 1964
An Honest Shuffle
TypeScript·1964·28 lines·836 bytes
/**
* Fisher-Yates — walk backwards, swapping each element with one drawn from
* the part not yet visited.
*/
// Seeded, so the museum's copy shuffles the same way every time. A real
// shuffle deserves a better source of randomness than this; the loop below is
// what is on display.
let state = 2463534242;
const random = (): number => {
state ^= state << 13;
state ^= state >>> 17;
state ^= state << 5;
return (state >>> 0) / 4294967296;
};
function shuffle<T>(items: readonly T[]): T[] {
const xs = [...items];
for (let i = xs.length - 1; i > 0; i--) {
// j is drawn from 0..i inclusive — including i, which is what makes
// every arrangement equally likely.
const j = Math.floor(random() * (i + 1));
[xs[i], xs[j]] = [xs[j], xs[i]];
}
return xs;
}
console.log(shuffle([1, 2, 3, 4, 5, 6, 7, 8]).join(" "));Curator’s note
Almost nobody writes this. What people write is items.sort(() => Math.random() - 0.5), and it is wrong — not inefficient, not inelegant, wrong. It produces some orderings far more often than others, and which ones depends on the sorting algorithm underneath, so the bias is different between browsers and can change when a runtime is updated. It looks like a shuffle, passes a glance, and quietly favours certain outcomes forever.
The correct version is four lines and the crucial detail is the inclusive bound. Drawing j from 0..i gives every permutation equal probability; drawing it from 0..n-1 instead — the mistake that is one character away — produces a distribution that is visibly skewed for as few as three elements. This is the rare case where a correctness argument fits in a sentence: at each step, one item is chosen uniformly from those not yet placed, so every arrangement can be reached exactly one way.
The shuffle is only ever as fair as the numbers feeding it, which is why this file ships a toy generator with a warning attached rather than pretending. A seeded shuffle is exactly what a museum wants — the same arrangement on every visit — and exactly what a card game does not.
The names are worth the plaque. Fisher and Yates published it in 1938 as a procedure for people with pencil and paper and a table of random numbers. Durstenfeld gave it the in-place, linear form in 1964. Knuth put it in *The Art of Computer Programming*, which is why half the profession calls it the Knuth shuffle and the other half corrects them.