Skip to content

Fisher-Yates shuffle

A way to shuffle a list in one pass so that every possible order is equally likely.

Also called Knuth shuffle.

Walk backwards through the list. At each position, pick a random spot from the start up to and including where you are, then swap the two.

js
for (let i = a.length - 1; i > 0; i--) {
  const j = Math.floor(rand() * (i + 1));
  [a[i], a[j]] = [a[j], a[i]];
}

The classic bug is picking from the whole list every time, or sorting with () => Math.random() - 0.5. Both look random. Both quietly make some orders more likely than others. In a sweepstake, that's a rigged draw nobody meant to rig.

Hattle, my World Cup sweepstake app, used it to deal all 48 teams out to a group. The rand there wasn't Math.random(), though. It was seeded, so any draw can be re-run and checked.

Related:Seeded randomness.

Where I've used it: