Shuffle a list

A genuinely uniform shuffle, and the arithmetic that shows why the version almost everybody writes cannot be one — nⁿ paths do not divide evenly into n! orderings. Nothing you type here leaves your browser — it is worked out on your own device, so there is nothing to send and nothing to log.

This page will not fall back to Math.random(). Everything here is drawn from crypto.getRandomValues(), which the browser backs with the operating system's cryptographic source. If that is unavailable the page says so and produces nothing — because output from a weak source looks exactly like output from a strong one, and that is the whole problem.

The shuffle everybody writes cannot be fair, and that is arithmetic

This is the version that turns up in answers, tutorials and production code:

for (i = 0; i < n; i++)
    swap(a[i], a[random 0..n-1]);

It looks right. Every position gets swapped, the index is random, the output is jumbled. It is not uniform, and no amount of running it will make it so.

Count the paths. The loop makes n independent choices out of n possibilities, so there are nⁿ equally likely ways through it. There are n! possible orderings. For the counts to come out even, n! would have to divide nⁿ — and it never does for n of 3 or more.

At five items one ordering is nearly three times as likely as another. That is not a rounding error and it does not average out.

Fisher-Yates, which does work

The fix is one character wide: draw from the part of the list not yet settled, rather than from the whole thing.

for (i = n-1; i > 0; i--)
    swap(a[i], a[random 0..i]);

Now the number of paths is n × (n−1) × … × 1 = n!, exactly one per ordering. Enumerate all twenty-four paths for four items and every ordering appears exactly once. That is what this page uses.

And sorting by a random comparator is worse still

The other common answer is

list.sort(() => Math.random() - 0.5);

which is not merely biased. A comparator is supposed to give the same answer about the same pair every time, and to be consistent between pairs. This one is neither, so the sort algorithm's assumptions are broken and the result depends on which sort the browser happens to use.

Measured in V8 — Chrome, Edge and Node — over 120,000 shuffles of four items, it gives a chi-square of around 138,000 on 23 degrees of freedom. A fair shuffle sits near 23. Firefox and Safari give different wrong answers, because they sort differently.

It reaches all twenty-four orderings, which is exactly why nobody notices: the output looks shuffled.

Where the randomness comes from

From crypto.getRandomValues(), which the browser backs with the operating system's cryptographic random source, and the index is drawn by rejecting the uneven tail of the range rather than taking a remainder. If that source is missing, this page says so and produces nothing, because a quiet fall back to Math.random() would look identical and would not be the same.

There is no seed, deliberately. A shuffle you can reproduce is a shuffle somebody else can predict.

Where to go next

Pick one at random · Random numbers · Dice