Introduction

The naive shuffle algorithm — swapping each element with a randomly chosen element from the entire array — produces biased results because it generates n^n possible swap sequences for n elements, but there are only n! permutations. Since n^n is not evenly divisible by n! (for n > 2), some permutations are produced more often than others. The correct algorithm is the Fisher-Yates (Knuth) shuffle, which restricts each swap to the remaining unshuffled portion of the array, generating exactly n! equally likely outcomes.

The Naive (Biased) Shuffle

1import random
2
3def naive_shuffle(arr):
4    n = len(arr)
5    for i in range(n):
6        j = random.randint(0, n - 1)  # BUG: picks from entire array
7        arr[i], arr[j] = arr[j], arr[i]
8    return arr

For an array of 3 elements, this algorithm has 3^3 = 27 possible outcomes (3 choices at each of 3 steps). But there are only 3! = 6 permutations. Since 27 is not divisible by 6 evenly (27 / 6 = 4.5), some permutations must appear more frequently than others.

Demonstrating the Bias

1from collections import Counter
2
3def count_permutations(shuffle_fn, arr, trials=1_000_000):
4    counts = Counter()
5    for _ in range(trials):
6        copy = arr[:]
7        shuffle_fn(copy)
8        counts[tuple(copy)] += 1
9    return counts
10
11# Compare naive vs Fisher-Yates
12arr = [1, 2, 3]
13naive_counts = count_permutations(naive_shuffle, arr)
14print("Naive shuffle distribution:")
15for perm, count in sorted(naive_counts.items()):
16    print(f"  {perm}: {count:6d} ({count/1_000_000*100:.2f}%)")
17
18# Expected for unbiased: each permutation ~16.67% (1/6)
19# Naive shuffle: some are ~14.8%, others ~18.5%

Running this with 1 million trials reveals significant deviation from the expected uniform distribution.

Why n^n Cannot Be Uniform Over n!

For n = 3:

• Naive shuffle: 3^3 = 27 equally likely swap sequences
• Permutations: 3! = 6
• 27 / 6 = 4.5 — not an integer

Since 27 sequences cannot be divided evenly into 6 groups, at least one permutation must be overrepresented. Specifically:

• 3 permutations appear in 5 out of 27 sequences (18.5%)
• 3 permutations appear in 4 out of 27 sequences (14.8%)

For larger arrays, the bias compounds. With n = 52 (a deck of cards), 52^52 possible outcomes mapped to 52! permutations produces extreme bias.

The Fisher-Yates Shuffle (Correct)

1import random
2
3def fisher_yates_shuffle(arr):
4    n = len(arr)
5    for i in range(n - 1, 0, -1):
6        j = random.randint(0, i)  # Pick from remaining unshuffled portion
7        arr[i], arr[j] = arr[j], arr[i]
8    return arr
9
10# Or the forward variant (Durstenfeld)
11def durstenfeld_shuffle(arr):
12    n = len(arr)
13    for i in range(n - 1):
14        j = random.randint(i, n - 1)  # Pick from i to end
15        arr[i], arr[j] = arr[j], arr[i]
16    return arr

Fisher-Yates generates exactly n! outcomes: at step 1 there are n choices, at step 2 there are n-1 choices, and so on. The product n * (n-1) * ... * 1 = n!, and each path maps to exactly one permutation.

Verifying Fisher-Yates Is Unbiased

1fy_counts = count_permutations(fisher_yates_shuffle, [1, 2, 3])
2print("Fisher-Yates distribution:")
3for perm, count in sorted(fy_counts.items()):
4    print(f"  {perm}: {count:6d} ({count/1_000_000*100:.2f}%)")
5
6# Each permutation appears ~166,667 times (16.67%)
7# (1, 2, 3): 166,534 (16.65%)
8# (1, 3, 2): 166,891 (16.69%)
9# (2, 1, 3): 166,721 (16.67%)
10# ... all within statistical noise

Python's Built-in Shuffle

1import random
2
3arr = [1, 2, 3, 4, 5]
4random.shuffle(arr)  # In-place Fisher-Yates shuffle
5print(arr)
6
7# For a new shuffled copy without modifying the original
8original = [1, 2, 3, 4, 5]
9shuffled = random.sample(original, len(original))
10print(original)  # Unchanged
11print(shuffled)  # Shuffled copy

Python's random.shuffle() implements Fisher-Yates internally. Always use the standard library function rather than writing your own.

Other Incorrect Shuffle Variants

1# WRONG: Sort with random comparator
2arr.sort(key=lambda x: random.random())
3# This is O(n log n) and technically produces a valid permutation,
4# but the distribution depends on the sort algorithm and may be biased
5
6# WRONG: Swap adjacent elements randomly
7for i in range(len(arr) - 1):
8    if random.random() > 0.5:
9        arr[i], arr[i+1] = arr[i+1], arr[i]
10# This is a random bubble sort pass — cannot produce all permutations
11
12# CORRECT: Use the standard library
13random.shuffle(arr)

Implementation in Other Languages

1// JavaScript — Fisher-Yates
2function shuffle(arr) {
3    for (let i = arr.length - 1; i > 0; i--) {
4        const j = Math.floor(Math.random() * (i + 1));
5        [arr[i], arr[j]] = [arr[j], arr[i]];
6    }
7    return arr;
8}

1// Java — use Collections.shuffle
2import java.util.Collections;
3import java.util.ArrayList;
4
5ArrayList<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4, 5));
6Collections.shuffle(list);

Common Pitfalls

• Using random.randint(0, n-1) instead of random.randint(0, i): The key difference between the naive and Fisher-Yates shuffles is the range of the random index. Picking from the entire array (0 to n-1) at every step causes bias. Picking from the remaining unshuffled range (0 to i or i to n-1) produces uniform results.
• Off-by-one errors in the Fisher-Yates loop: The backward variant loops from n-1 down to 1 (not 0), picking j in [0, i]. The forward variant loops from 0 to n-2, picking j in [i, n-1]. Including or excluding the wrong boundary shifts the distribution.
• Using Math.random() * n without Math.floor() in JavaScript: Math.random() returns a float in [0, 1). Without Math.floor(), you get a float index that JavaScript silently converts, potentially causing incorrect behavior.
• Assuming sort-based shuffling is correct: Sorting with random keys (arr.sort(() => Math.random() - 0.5)) is a common pattern in JavaScript tutorials, but the distribution depends on the sort algorithm's comparison patterns and is not guaranteed to be uniform.
• Not understanding that bias matters in practice: For a deck of 52 cards, the naive shuffle favors certain orderings over others. In games, gambling, cryptographic applications, or scientific simulations, this bias can be exploited or produce invalid results.

Summary

• The naive shuffle (swap with any random index) is biased because n^n swap sequences cannot map uniformly to n! permutations
• Fisher-Yates (Knuth) shuffle is correct: at each step, swap with a random element from the unshuffled portion only
• The total number of Fisher-Yates outcomes is n * (n-1) * ... * 1 = n!, with each permutation appearing exactly once
• Use standard library functions (random.shuffle in Python, Collections.shuffle in Java) — they implement Fisher-Yates
• Sort-based shuffling and adjacent-swap methods are also biased or incomplete — avoid them