# What is the Fisher-Yates shuffle?

> The Fisher-Yates shuffle, also called the Knuth shuffle, permutes an array uniformly at random in one pass. The algorithm and the bug most people write.

**Fisher-Yates shuffle**: The Fisher-Yates shuffle produces a uniformly random permutation of an array in one pass by swapping each position with a randomly chosen position at or before it.

The **Fisher-Yates shuffle** (often called the **Knuth shuffle**, since it appears as Algorithm P in TAOCP §3.4.2) shuffles an array of n items so that all n! orders are equally likely, in one pass and with no extra memory.

## The algorithm

```
for i from n - 1 down to 1:
    j = random integer with 0 <= j <= i
    swap a[i] and a[j]
```

Each step fixes the item in the last unfixed position, chosen uniformly from the items not yet placed. There are n choices, then n - 1, and so on, which gives exactly n! equally likely outcomes.

## The common bug

Picking j from the whole array every time (0 to n - 1 instead of 0 to i) looks harmless but is biased: it has n^n equally likely runs, which cannot divide evenly among n! permutations. A second classic bias is `rand() % k` when the generator's range is not a multiple of k. Both are covered in [§3.4.2](https://cracked.guide/guide/knuth-w055-0) along with reservoir sampling, for choosing k items from a stream of unknown length.

## Questions

### Why is it called the Knuth shuffle?

Fisher and Yates published a pencil-and-paper version in 1938; Durstenfeld gave the computer version in 1964; Knuth popularized it in TAOCP.

---

Source: https://cracked.guide/glossary/fisher-yates-shuffle
cracked.guide: A free, dated 145-week path to getting genuinely cracked at programming.