Fisher–Yates shuffle — Give every order the same chance

01 / The idea

Every order should have the same chance.

Three tracks can play in six orders. A fair shuffle is one where each of those six is equally likely, 1 in 6, every time someone presses the button. That’s the whole promise. It says nothing about a single shuffle looking random: A, B, C is exactly as likely as any other order.

One million runs of `tracks.sort(() => Math.random() - 0.5)` on A, B, C, measured in Node 22.21.1. A fair shuffle gives each order about 166,667.
Order	Times	Share
A, B, C	375,037	37.5%
A, C, B	62,256	6.2%
B, A, C	124,912	12.5%
B, C, A	62,543	6.3%
C, A, B	62,129	6.2%
C, B, A	313,123	31.3%

The sort isn’t broken. It was never asked to shuffle. A sort expects its comparator to answer the same question the same way every time. Ours flips a coin on every comparison, so the order depends on which comparisons that particular sort happens to make, and a sort makes very particular ones.

What does the language specification say?A comparator has to be consistent

ECMAScript defines a consistent comparator, which includes: “Calling comparator(a, b) always returns the same value v when given a specific pair of values a and b as its two arguments.” A coin flip breaks that on its first repeat. The consequence is spelled out in the same section: “The sort order is implementation-defined if SortCompare is not a consistent comparator for the elements of items.”

So the table above describes one engine, not JavaScript. With four tracks the same engine gave A, B, C, D 187,728 times out of a million and B, C, D, A 15,447 times, where a fair shuffle gives each of the 24 orders about 41,667.

02 / Name the rule

Pick from what’s left. Then set it aside.

Fisher–Yates settles one position at a time, starting from the end. The last position takes a track chosen fairly from all of them; the next takes one chosen from everything still unplaced. Every choice is final.

With four tracks, position 3 draws from 4, position 2 from 3, position 1 from 2, and position 0 keeps the one track left. A draw may pick the track already sitting in that position. It stays where it is. Rule that out and a track could never end up where it started.

03 / Follow one operation

Four tracks, three draws.

Watch seed 10 shuffle four tracks, step through each draw, then open Try it and use your own seed. Try it also counts every possible sequence of draws, for the fair rule and for a tempting one.

Playback controls

Fisher–Yates

Pick from what’s left. Then set it aside.

0 A Harbor Lights
1 B Paper Moon
2 C Night Bus
3 D Slow Tide

the draw range starts at the last position

01/ 03

Pick from what’s left

Four tracks, nothing settled yet.

Start at the last position. Any of the four tracks could end up there.

Reduced motion: choose a scene to see its completed state.

Read this scene

Start at the last position. Any of the four tracks could end up there.

Start at the last position. Any of the four tracks could end up there. Order: 0: Harbor Lights, 1: Paper Moon, 2: Night Bus, 3: Slow Tide.

Try the example by reading

Four tracks start as Harbor Lights, Paper Moon, Night Bus, Slow Tide. Position 3 draws from 4 and picks 2, so Night Bus swaps to the end. Position 2 draws from 3 and picks 0, so Harbor Lights swaps into position 2. Position 1 draws from 2 and picks itself, so Paper Moon stays. Position 0 keeps Slow Tide. With three tracks, Fisher–Yates has 6 draw sequences, one per order; swapping with any position has 27, and each order gets 4 or 5.

Tracks Seed, 1 to 4294967295

Rule Fisher–Yates Swap with any position

Nothing drawn yet. The first draw is for position 3.

Every draw sequence, run once

24 equally likely sequences for 4 tracks. Each order is reached exactly 1 time: every order has the same chance.

ABCD1
ABDC1
ACBD1
ACDB1
ADBC1
ADCB1
BACD1
BADC1
BCAD1
BCDA1
BDAC1
BDCA1
CABD1
CADB1
CBAD1
CBDA1
CDAB1
CDBA1
DABC1
DACB1
DBAC1
DBCA1
DCAB1
DCBA1

Or shuffle 60,000 times

A sample from the seeded generator. It supports the count above; it doesn’t prove it.

Watch and Step through replay seed 10. Try it runs the same TypeScript with your own seed and starts fresh each time you open it.

04 / Read the shape

Six orders need six equal ways in.

Here is why that’s fair, with no statistics at all. For three tracks the draws come from 3, then from 2: 3 × 2 = 6 possible draw sequences, each as likely as the others. Two different sequences can’t end in the same order, because the first draw decides the last track and the second decides the middle one. Six sequences, six orders, one each. The Basic form below is that walk, with the tempting version under it.

Read in

Compare with

Fisher–Yates walks from the end, drawing each position’s track from the unsettled front. Below it, the tempting version swaps every position with any position; it is here to be counted.

TypeScriptReading

playlist.ts

// Fisher–Yates. Settle positions from the end: position i takes a track chosen
// from everything not yet settled, positions 0 through i, i itself included.
export function shuffle<T>(items: readonly T[], draw: Draw): T[] {
	const order = [...items];
	for (let i = order.length - 1; i > 0; i--) {
		const j = pick(draw, i + 1);
		[order[i], order[j]] = [order[j], order[i]];
	}
	return order;
}

// The tempting version: swap every position with any position. n draws of n make
// nⁿ equally likely runs, and for n > 2 they can't split evenly across n! orders.
export function swapWithAny<T>(items: readonly T[], draw: Draw): T[] {
	const order = [...items];
	for (let i = 0; i < order.length; i++) {
		const j = pick(draw, order.length);
		[order[i], order[j]] = [order[j], order[i]];
	}
	return order;
}

GoAlongside

playlist.go

// Fisher–Yates. Settle positions from the end: position i takes a track chosen
// from everything not yet settled, positions 0 through i, i itself included.
func Shuffle[T any](items []T, draw Draw) ([]T, error) {
	order := make([]T, len(items))
	copy(order, items)
	for i := len(order) - 1; i > 0; i-- {
		j, err := pick(draw, i+1)
		if err != nil {
			return nil, err
		}
		order[i], order[j] = order[j], order[i]
	}
	return order, nil
}

// The tempting version: swap every position with any position. n draws of n make
// nⁿ equally likely runs, and for n > 2 they can't split evenly across n! orders.
func SwapWithAny[T any](items []T, draw Draw) ([]T, error) {
	order := make([]T, len(items))
	copy(order, items)
	for i := range order {
		j, err := pick(draw, len(order))
		if err != nil {
			return nil, err
		}
		order[i], order[j] = order[j], order[i]
	}
	return order, nil
}

The rule every step keeps: each way of filling the settled positions is equally likely, and the unsettled front holds exactly the tracks not yet placed. The next draw picks fairly from that front, so the rule still holds one position later. When the front is a single track, every position is settled and every order had the same chance.

Now the tempting version: at every position, swap with any position in the whole list. It feels like more mixing. For three tracks it makes 3 × 3 × 3 = 27 equally likely runs, and 27 can’t be split into six equal shares. Counting them gives 4, 5, 5, 5, 4, 4.

For n tracks that’s nⁿ runs over n! orders. From three tracks on, n! includes the factor n − 1, which shares no factor with n, so nⁿ can never be divided evenly among the orders. More mixing, less fairness.

A fair pick needs a fair bound.

Every count so far assumed each draw is fair: a whole number from 0 to i, each equally likely. That’s easy to get almost right. A generator gives you 32 random bits, a number below 4,294,967,296, and value % bound always lands in range. It lands unevenly whenever 4,294,967,296 isn’t a multiple of the bound.

For a bound of 3 the tilt is one extra value for 0 out of 4,294,967,296. For a bound of 3,000,000,000 it’s enormous: every result below 1,294,967,296 would be twice as likely as the rest. The fix is to throw away values from the uneven slice at the top and draw again. Less than half of all values are ever thrown away, so a draw takes fewer than two tries on average. The In the wild tab above shows drawBelow right after the generator.

You don’t have to write this in Go. The standard library’s math/rand/v2 Shuffle is this walk, comment and all: // Fisher-Yates shuffle, then a loop from n - 1 down to 1 that draws j below i + 1 and swaps. JavaScript has no built-in shuffle, which is how the sort one-liner gets written.

Why does this lesson bring its own generator?Repeatable seeds, and what not to use them for

Math.random() can’t replay a shuffle. MDN: “The implementation selects the initial seed to the random number generation algorithm; it cannot be chosen or reset by the user.” Tests, a second device, and the story above all need the same order from the same seed, so the lesson uses a 32-bit xorshift generator, from the family George Marsaglia described in “Xorshift RNGs” (2003), written identically in TypeScript and Go.

None of these are for secrets. MDN says Math.random() “does not provide cryptographically secure random numbers” and points to Crypto.getRandomValues(). Go’s math/rand/v2 documentation says it “should not be used for security-sensitive work” and points to crypto/rand. A tiny xorshift generator is weaker than either. When an order must be unpredictable, such as a prize draw, use those.

Reading the TypeScriptA draw you pass in, and an unsigned shift

shuffle is generic over T and takes the draw as a function, Draw = (bound: number) => number. Tests hand it every sequence of draws in turn; the page and the playlist hand it a seeded one. It copies the list with a spread and swaps with array destructuring.

xorshift32 keeps its state in a closure. JavaScript’s shift operators work on signed 32-bit numbers, so each step ends with state >>>= 0 to turn the result back into an unsigned one. Errors are a ShuffleError whose code matches the Go version.

Reading the GoGenerics, an error from every draw, and uint64

Shuffle and SwapWithAny are generic, [T any], and return ([]T, error): a draw that returns a number out of range is refused as bad-draw instead of panicking on the index.

The generator is a closure over a uint32, so its shifts wrap on their own. DrawBelow works in uint64, where 2³² itself fits. Seeds are int64, so 4294967295 fits and a negative seed can be refused rather than wrapping. Errors are a *ShuffleError with the same codes.

What is refusedSeeds, playlists, ids, and draws

A seed is a whole number from 1 to 4294967295 (bad-seed); zero is refused because a xorshift generator started at zero stays at zero. A playlist holds up to 64 tracks (too-many-tracks). Every track needs an id (empty-id), and no id may appear twice (duplicate-id). playOrder checks in that order: the seed, the length, then each track in turn. A draw that returns anything but a whole number below its bound is bad-draw.

The exact counts run every draw sequence for 1 to 6 tracks, up to 46,656 runs. Try it uses 3 to 6 tracks and samples 60,000 shuffles.

05 / Try a decision

Which rewrite breaks the promise?

Three teammates each changed the shuffle. Decide which one is unfair before the feedback tells you.

06 / Follow the cost

One pass, and a seed with limits.

Fisher–Yates: time and extra space, with n tracks
Operation	Time	Extra space	What it assumes
Shuffle n tracks	`O(n)`	`O(n)`	n − 1 draws and n − 1 swaps. The copy keeps the caller’s list as it was; shuffling in place needs O(1).
One fair draw	`O(1) expected`	`O(1)`	Fewer than two generator calls on average: less than half of all values are ever thrown away.
Pick k of n	`O(n)`	`O(n)`	Run k steps and take the settled tail. The O(n) is the copy; in place, the k steps cost O(k).
Sort by random keys	`O(n log n)`	`O(n)`	Also fair while no two keys tie, but it sorts and keeps a number per track.
Count every draw sequence	`O(n · n!)`	`O(n · n!)`	What the tests do for 1 to 6 tracks: every sequence runs once and every order is counted. Swap-with-any has nⁿ sequences instead, 46,656 at six tracks.

The copy is a choice, not part of the algorithm. Shuffled in place, the list needs no extra space, and the caller’s list changes under them, which is why shuffle copies.

The generator sets a different limit. A 32-bit seed has 4,294,967,295 usable values, so one generator can produce at most that many different shuffles. Twelve tracks have 479,001,600 orders; thirteen have 6,227,020,800. From thirteen tracks on, some orders can never come out of this generator, and by twenty almost none can. For a playlist nobody will notice. Go’s source makes the same point about its own generators, for lists too long to fit 32 bits: “there's no way that any PRNG can have a big enough internal state to generate even a minuscule percentage of the possible permutations.”

07 / Give it a real job

Shuffle the session once, and remember how.

A music app shuffles a playlist when someone presses Shuffle. From then on, Previous has to go back to the track they just heard, a reload shouldn’t reshuffle, and the phone and the laptop should agree on what plays next. Shuffling again at each of those moments breaks all three.

So the app shuffles once, keeps the seed with the listening session, and asks for the order again whenever it needs it. The wrapper checks what the shuffle can’t: every track has an id, no id appears twice, and the playlist fits the limit. Switch the examples to In the wild for playOrder, and to At the call site for a program that uses it; Complete files has both whole programs.

Both versions print harbor blue paper tide bus twice, then the exact counts for three tracks: 1 each for Fisher–Yates, and 4, 5, 5, 5, 4, 4 for swapping with any position.

Build UIs?That one-liner lives in components, and server rendering adds a second way for it to go wrong.

Where it already is in your components

The one-liner from the top of this page is at home in a component: shuffle the quiz answers, the featured cards, the “you might also like” row. Put it in the render path of a server-rendered page and it goes wrong a second way. The server shuffles once to build the HTML, the browser shuffles again while hydrating, and the two orders disagree.

React’s docs say the tree you hydrate “needs to produce the same output as it did on the server,” and its mismatch error lists the usual suspects, including “Variable input such as Date.now() or Math.random() which changes each time it’s called.” React recovers from some of these, but the docs are plain about it: “you must fix them like other bugs.” SvelteKit works the same way by default: it “renders your page on the server before sending that HTML to the client where it’s hydrated,” so a shuffle in a component’s script runs in both places.

When you have to own it

A quiz app shuffles each question’s choices so neighbors don’t share answer positions. The order has to be the same on the server, in the browser, after a reload, and on the review screen where the student sees what they picked. Each of those knows the attempt and the question. None of them knows the others’ Math.random().

So derive the seed from those IDs and run the fair shuffle. The snippet hashes them with FNV-1a, the same hash the Hash set lesson uses, and hands the result to this lesson’s generator.

quiz-order.ts

import { seededDraw, shuffle } from '../playlist';

export type Choice = { id: string; text: string };

// One attempt must show the same order on the server, in the browser, after a reload,
// and on the review screen. Math.random() gives each of them its own order, so derive
// the seed from data all of them already have.
export function seedFor(key: string): number {
	let hash = 2166136261; // FNV-1a over the key's UTF-8 bytes
	for (const byte of new TextEncoder().encode(key)) {
		hash ^= byte;
		hash = Math.imul(hash, 16777619) >>> 0;
	}
	return hash === 0 ? 1 : hash; // the generator needs a nonzero seed
}

export function choiceOrder(
	choices: readonly Choice[],
	attemptId: string,
	questionId: string
): Choice[] {
	return shuffle(choices, seededDraw(seedFor(`${attemptId}/${questionId}`)));
}

A derived order is repeatable on purpose, so anyone with the IDs and this code can work it out. If the order must be unpredictable, choose it on the server with a cryptographic source, crypto.getRandomValues() in Node or crypto/rand in Go, and store the order with the attempt. If the order can wait until the page is interactive, React’s docs also show a two-pass render that switches after hydration. The rule is the same in React and Svelte, so one snippet serves both.

08 / Make the call

Shuffle when you need the whole order.

Reach for Fisher–Yates when every item needs a place and every order should be equally likely: a playlist, a quiz’s answer choices, a deck of cards, the order of tasks in a study.

Something smaller may do. To pick one item, make one draw below the list’s length. To pick k items from a list you already hold, run Fisher–Yates for k steps and take the settled tail; nothing else needs to move. If items arrive as a stream of unknown length, reservoir sampling keeps a fair sample without storing them all. If some items should come up more often, that’s a weighted choice, a different problem.

Watch for rules added after the shuffle. “Never start with the track that just ended” sounds harmless, but swapping that track away changes the chances of every order. Decide whether the rule matters more than the fairness, and write that down.

SourcesThe specification, the standard libraries, and the docs

ECMAScript 2025, SortIndexedProperties, defines a consistent comparator and makes the sort order implementation-defined without one.
Go 1.24.0, math/rand/v2 Shuffle, and the package comment on security-sensitive work.
MDN on Math.random() and Crypto.getRandomValues().
George Marsaglia, “Xorshift RNGs”, Journal of Statistical Software 8(14), 2003.
React’s hydrateRoot docs and the react-dom 19.1.0 mismatch message; SvelteKit’s ssr page option.

All checked 13 September 2026. The sort measurements are one run in Node 22.21.1.

09 / Take the idea with you

Explain a fair shuffle without saying “Fisher–Yates.”

“Walk from the end. Each position takes a track drawn fairly from everything not yet placed, itself included. n − 1 fair draws make n! equally likely sequences, one for each order.”

Then explain the page: “The seed lives with the session or the attempt, so every screen that shows the order agrees.”

Before moving on, search your code for Math.random() - 0.5. Now you know what that line was really doing.

Connections to follow nextRelated lessons

Dynamic array is the array this shuffle swaps in place.
Hash set uses FNV-1a, the hash behind the quiz seed.
Reservoir sampling picks fairly from a stream whose length you don’t know, and uses this lesson’s draws.