What is the Fisher-Yates shuffle?

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 along with reservoir sampling, for choosing k items from a stream of unknown length.