Heap's Algorithm

Generating all permutations with minimal swaps

How do you generate every possible arrangement of a set of elements? The naive approach copies and rearranges repeatedly. But there's a beautiful algorithm discovered by B.R. Heap in 1963 that does something remarkable: it generates each new permutation by swapping just two elements.

This means to generate all 24 permutations of [A,B,C,D], Heap's algorithm performs exactly 23 swaps. One swap, one new arrangement. No wasted motion.

Start Simple: Two Elements

With just two elements, there are only two permutations:

[A, B]

swap 0↔1

[B, A]

One swap. Done. Now let's add a third element.

Three Elements: The Pattern Emerges

With three elements, we have 3! = 6 permutations. Watch what Heap's algorithm does:

Click Play or Step

ABC

Notice the pattern: we generate all permutations where C is in the last position, then swap to put a different element there, and repeat.

The Key Insight

Heap's algorithm is recursive. To permute n elements:

Generate all permutations of the first n-1 elements (keeping the last element fixed)
Swap to bring a new element into the last position
Repeat until every element has had a turn in the last position

Permute 3 elements:

[ permute A,B ] C

→ swap →

[ permute B,C ] A

→ swap →

[ permute C,A ] B

But here's the puzzle: which element should we swap into the last position each time?

The Parity Rule

This is where Heap's genius shows. The swap rule depends on whether n is even or odd:

When n is odd

0 1 2 n-1

Always swap first element with last

When n is even

i ... n-1

Swap position i with last (i goes 0, 1, 2, ...)

Why these specific rules? They're not arbitrary—they're the only rules that work.

Why Parity Matters

Think of nested gears in a clock. If two adjacent gears spin the same direction, they grind. They must spin opposite directions to mesh properly.

n even
rotates through positions

⚙

n-1 odd
pivots on position 0

The same principle applies here. After the recursive call returns, the first n-1 elements are in a specific state that depends on parity:

If n-1 is odd: elements return to ~original order Rotate through positions to create new combinations

If n-1 is even: elements end up shuffled differently Use fixed position (inner provides the variation)

The one-liner: When inside rotates, outside pivots. When inside pivots, outside rotates.

Four Elements: See It All Together

Now watch the full algorithm on four elements. Notice how the parity rule creates a meshing pattern between levels:

Speed:

Click Play or Step

k=4

ABCD

Permutations: 1/24 Swaps: 0

The Code

The entire algorithm in just a few lines:

function heapPermute(arr, n = arr.length) {
    if (n === 1) {
        output(arr);
        return;
    }

    for (let i = 0; i < n; i++) {
        heapPermute(arr, n - 1);

        if (i < n - 1) {  // don't swap after last iteration
            if (n % 2 === 0) {
                swap(arr, i, n - 1);
            } else {
                swap(arr, 0, n - 1);
            }
        }
    }
}

That's it. The parity check n % 2 === 0 is the entire secret. Everything else is just recursion and a loop.

Why This Matters

Heap's algorithm achieves the theoretical minimum: n! - 1 swaps for n! permutations. Each swap produces exactly one new arrangement. This makes it:

Cache-friendly: Only two elements move at a time
Minimal memory: Works in-place, no copying needed
Simple to implement: Just recursion + parity check

The deeper lesson: sometimes the right abstraction makes a complex problem trivial. Heap found that parity—the simplest property of numbers—perfectly captures what's needed to navigate the space of permutations.