Algorithms - Fisher-Yates Shuffle

The Fisher-Yates shuffle (also modernized by Richard Durstenfeld and Donald Knuth) is an algorithm for generating a random permutation of a finite sequence in O(n) time and O(1) auxiliary space.

Every possible permutation of the array has an equal probability (1 / n!) of occurring.

How the Algorithm Works

1. Start from the last element (index n - 1) and iterate backward to index 1.
2. In each iteration at index i, pick a random integer j uniformly from the range [0, i] (inclusive).
3. Swap elements at index i and index j.
4. Decrement i and repeat until the beginning of the array.

Initial:      [ A,  B,  C,  D ]  (i = 3, pick j in [0, 3] -> say j=1)
Swap(3, 1):   [ A,  D,  C, (B)]  (i = 2, pick j in [0, 2] -> say j=0)
Swap(2, 0):   [ C,  D, (A), (B)] (i = 1, pick j in [0, 1] -> say j=1)
Swap(1, 1):   [ C, (D), (A), (B)] (Done! Permutation: C, D, A, B)

Mathematical Proof of Uniformity

For an array of length n, there are n! possible permutations. The algorithm produces an unbiased uniform distribution because:

1. For the last position n - 1, there are n choices: P = 1/n.
2. For position n - 2, there are n - 1 remaining choices: P = 1/(n - 1).
3. For position n - 3, there are n - 2 choices: P = 1/(n - 2).
4. Repeating down to the first element yields:

   P(permutation) = (1/n) × (1/(n-1)) × ... × (1/2) × (1/1) = 1/n!
   

The Naive Shuffle Anti-Pattern (A Common Bug)

A notorious pitfall is writing:

# BROKEN / BIASED: Do NOT do this!
for i in range(n):
    j = random.randint(0, n - 1)  # WRONG: picking from ALL indices [0, n-1]
    arr[i], arr[j] = arr[j], arr[i]

Why Naive Swapping is Biased

If an algorithm performs n random swaps where each swap has n possible choices, the total number of decision outcomes is n^n.

For the distribution to be uniform, every permutation must appear an equal integer number of times:

n^n / n! must be an integer

However, for any n > 2, n^n is never divisible by n! (because n! contains prime factors not in n). Therefore, some permutations will inevitably occur more frequently than others, creating measurable statistical bias.

Implementations

Python

import random

def shuffle(arr: list) -> None:
    for i in range(len(arr) - 1, 0, -1):
        j = random.randint(0, i)
        arr[i], arr[j] = arr[j], arr[i]

Go

package main

import "math/rand/v2"

func Shuffle[T any](slice []T) {
    for i := len(slice) - 1; i > 0; i-- {
        j := rand.IntN(i + 1)
        slice[i], slice[j] = slice[j], slice[i]
    }
}

Java

public class ShuffleUtils {
    public static void shuffle(int[] a) {
        for (int i = a.length - 1; i > 0; i--) {
            int j = (int) (Math.random() * (i + 1));
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }
}

Complexity

Metric	Complexity
Time Complexity	O(n) (exactly n - 1 swaps)
Space Complexity	O(1) in-place auxiliary memory
Uniformity	Mathematically unbiased (P = 1 / n!)