Every other Probabilistic entry on this site either builds up state from a stream one item at a
time, replaces a rotation-based tree, or compares two items to each other. This one is simpler to
state than any of those: given an array of n items already fully in memory, produce
one permutation of it, chosen uniformly at random from all n! possibilities, touching
the array exactly once and using no extra memory beyond a loop counter and a swap. Reservoir Sampling solves a related-sounding
but genuinely different problem — picking a fair sample from a stream whose length isn't known in
advance. This entry assumes the opposite: the whole collection is already sitting in an array, its
length is already known, and the only question is what order to put it in.
The algorithm is named for Ronald Fisher and Frank Yates, who described the by-hand version in
1938 (cross out a name, roll dice, write it down, repeat). The in-place, O(n)
computer version below is Richard Durstenfeld's 1964 "inside-out" reformulation, popularized by
Knuth — different enough from the original pencil-and-paper procedure that it's sometimes called
the Knuth shuffle, but it produces the identical uniform guarantee the 1938 version proves, just
without ever needing a second array to cross names out of.
An 8-letter array, A through H, using a seeded random generator so the
trace is identical every time you replay it. Click Next to run one iteration of
the loop below — it swaps whichever position the loop is currently on with a uniformly drawn
position from everything not yet finalized (which can be itself), then locks that position in for
good and moves one step left. By the time the loop reaches position 0, every position has been
visited exactly once.
i from
array.length - 1 down to 1: draw j uniformly from
[0, i] (note the range includes i itself), then swap
array[i] and array[j]. Exactly n − 1 swaps, each
O(1), for a total of O(n) — and nothing is ever allocated beyond the
loop variables, so the extra space is O(1) regardless of n.O(n)
table build, every iteration here does the same fixed amount of work (one draw, one swap).Think of the loop as filling the array from the back forward, one position at a time.
When the loop reaches index i, exactly i + 1 items are still
"unplaced" — the ones currently sitting in positions 0 through i — and
the draw j ∈ [0, i] picks one of them, uniformly, to land in position i
for good. That item is never touched again. So: position n − 1 is filled by a uniform
choice among all n items (n possible outcomes), position n − 2
by a uniform choice among whichever n − 1 remain, and so on down to position
1, which chooses between the last 2, leaving position 0 with
whatever's left (1 possible outcome, forced). Every step's choice is independent of
every other step's, so the total number of equally likely choice sequences is
n × (n−1) × ... × 2 × 1 = n! — and because each step permanently removes exactly the
item it chose from all future choices, no two different choice sequences can ever produce the same
final arrangement. That's a bijection between choice sequences and permutations, and since every
choice sequence is equally likely, every permutation is too: probability exactly 1/n!,
proved here and checked against real trial counts below.
One detail that looks like it should be a special case but isn't: the draw range
[0, i] includes i itself, so roughly 1 time in
i + 1 a step "swaps" an item with itself and nothing visibly changes. That's not
wasted work to optimize away — it's required for the probabilities above to come out right. Leaving
it in keeps every one of the i + 1 unplaced items, including the one already sitting
at i, exactly as likely as any other to end up there. This is the same shape of mistake
as Reservoir Sampling's own off-by-one
pitfall (excluding the current item from a draw range "because it can't meaningfully choose
itself") — there, narrowing the range produces an exact, provable skew rather than a crash; the
same is true here, measured directly below.
function shuffle(array) {
for (let i = array.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1)); // uniform in [0, i]
[array[i], array[j]] = [array[j], array[i]];
}
return array;
}
Verified in Node before any page prose was written. (1) The exact shipped demo trace — all seven
iterations with the page's fixed seed reproduced standalone: i=7,j=5 ·
i=6,j=2 · i=5,j=1 · i=4,j=2 ·
i=3,j=3 (self-swap) · i=2,j=1 · i=1,j=0, taking
ABCDEFGH to EAHDGBCF, matching the page's own demo exactly. (2) A
600,000-trial frequency sweep at n=3 (small enough to enumerate every one of the
3! = 6 possible outputs) using real Math.random(): every permutation
landed within 0.001 of the theoretical 1/6 ≈ 0.1667. (3) The same sweep run against a
deliberately shrunk range (j drawn from [0, i-1] instead of
[0, i], dropping the self-swap case) confirmed the check would catch a broken
implementation: two permutations came back measurably underrepresented, the predicted effect of
narrowing the range described above. See the live trial button in Pitfalls below for the same
discipline exposed directly on the page, not just asserted in prose.
The single most common "shuffle" bug: drawing from the full range every step instead of shrinking it. It looks almost identical to the correct version:
// BROKEN: j drawn from the full [0, n) range every time, not shrinking to [0, i]
function naiveShuffle(array) {
for (let i = 0; i < array.length; i++) {
const j = Math.floor(Math.random() * array.length);
[array[i], array[j]] = [array[j], array[i]];
}
return array;
}
This one isn't just "biased in practice" — it's mathematically incapable of being uniform, for a
reason that doesn't need a single trial run to see. The loop makes n independent draws,
each with n equally likely outcomes, so there are exactly n^n equally
likely sequences of draws. For that to produce a uniform distribution over the n!
permutations, n! would have to divide n^n evenly — and at
n = 3, it already doesn't: 3^3 = 27 is not a multiple of
3! = 6. No implementation, no amount of care, no better random number generator can
fix that; the pigeonhole is the proof. Worked out exactly for n = 3 by enumerating all
27 equally likely draw-sequences directly: three of the six permutations (including the identity,
0,1,2) come out with probability 4/27 ≈ 0.1481, and the other three come
out at 5/27 ≈ 0.1852 — a real, exact, roughly 25% swing away from the correct
1/6 ≈ 0.1667 in both directions, not noise.
The second widely-copied idiom is worse, and the reason is different again:
// ALSO BROKEN: sorting with a random comparator is not a shuffle
array.sort(() => Math.random() - 0.5);
A comparator is supposed to answer a consistent question — "is A before or after B?" — and every
real sort algorithm relies on that consistency to decide which comparisons it even needs to make.
A comparator that answers randomly breaks that contract, so the result depends on the specific
sort algorithm's own internal comparison pattern, not on anything resembling a fair shuffle. The
exact bias is different in every JavaScript engine (V8, SpiderMonkey, JavaScriptCore each implement
Array.prototype.sort differently), which is itself worth noticing — a "shuffle" whose
fairness depends on which browser is running it was never actually a shuffle. One concrete
illustration, measured in this site's own Node (V8) environment at n = 3 across
600,000 trials: the identity permutation 0,1,2 came back 37.5% of the
time, against a correct 16.7% — more than double — while two other permutations
dropped to about 6% each.
Run all three live, in whatever browser is reading this page right now — the exact numbers for the sort-based row will likely differ from the 37.5%/16.7% figures above (different engine, same underlying mistake), but the correct Fisher–Yates row should land close to uniform regardless:
There is a correct sort-based shuffle — it's just slower, for no benefit. Assign
each item one fresh random number before sorting, store it, and sort by that fixed key
instead of calling Math.random() inside the comparator:
// CORRECT, but O(n log n): each item gets exactly one random key, fixed before the sort begins
function sortKeyShuffle(array) {
return array
.map(item => ({ item, key: Math.random() }))
.sort((a, b) => a.key - b.key)
.map(({ item }) => item);
}
Because every item's key is drawn once and never changes mid-sort, the comparator is consistent
again, and the final order is exactly as uniform as Fisher–Yates — confirmed in the same offline
Node sweep above, within 0.001 of 1/6 on every permutation at n=3. The
honest reason to prefer Fisher–Yates over this instead isn't correctness, it's that this version
costs O(n log n) comparisons and an extra array of keys to buy nothing a single
O(n) pass doesn't already give for free.
Time: O(n) — exactly n − 1 swaps, one random draw
each, regardless of the data. Space: O(1) extra, beyond the array
itself. The broken full-range version above costs exactly the same O(n) — fixing it
is free; the bug was never about speed. The correct sort-by-fixed-key alternative is the one real
time trade on this page: O(n log n) instead of O(n), plus an
O(n) array of keys, bought for no accuracy gain over plain Fisher–Yates.
This site's guide, Choosing a Probabilistic Structure, groups this entry with Alias Method as the two Probabilistic entries that answer a one-shot question about a whole, already-known collection rather than a stream, a tree, or a pairwise comparison — and compares what each of those two one-shot questions actually is.