Introduction

Heap's algorithm is a classic way to generate all permutations of a sequence by swapping elements in place. It is popular because the recursive rule is compact, it avoids repeatedly allocating new arrays, and it systematically visits every permutation exactly once.

The Core Idea of Heap's Algorithm

The algorithm works by generating permutations of the first n - 1 elements, then performing a swap that depends on whether n is odd or even, and repeating that process until every arrangement has been produced.

The recursive rule is:

1. if the current size is 1, emit the permutation
2. otherwise, generate permutations of size n - 1
3. after each recursive call, swap either the first element or the current element with the last one

That swap rule is the distinctive part of Heap's algorithm. It ensures the algorithm reaches every permutation without needing an explicit "used" array.

A Runnable Python Implementation

Here is a direct recursive implementation:

1def heaps_permutations(items, size=None):
2    if size is None:
3        size = len(items)
4
5    if size == 1:
6        print(items[:])
7        return
8
9    for i in range(size):
10        heaps_permutations(items, size - 1)
11
12        if size % 2 == 1:
13            items[0], items[size - 1] = items[size - 1], items[0]
14        else:
15            items[i], items[size - 1] = items[size - 1], items[i]
16
17
18values = [1, 2, 3]
19heaps_permutations(values)

For the input [1, 2, 3], this prints all six permutations. The list is modified in place during execution, which is one reason the algorithm is memory-friendly.

Why the Odd-Even Swap Rule Works

The swap rule looks arbitrary at first:

• when size is odd, swap the first element with the last active element
• when size is even, swap the current loop index with the last active element

This rule rotates which element moves into the active position for the next recursive branch. Without it, the recursion would revisit the same orderings or miss valid permutations.

A small example with [1, 2, 3] helps. The recursive call on size 2 generates permutations for the first two positions. After that, the size 3 frame swaps the first element with the last one, which introduces a new element at the end position and lets the next recursion branch build a new set of permutations.

You do not need to memorize every intermediate state, but you do need to understand that the swap pattern is what avoids duplicates.

A Generator Version

If you want to use the permutations lazily instead of printing them immediately, a generator is more useful:

1def generate_heaps(items, size=None):
2    if size is None:
3        size = len(items)
4
5    if size == 1:
6        yield items[:]
7        return
8
9    for i in range(size):
10        yield from generate_heaps(items, size - 1)
11
12        if size % 2 == 1:
13            items[0], items[size - 1] = items[size - 1], items[0]
14        else:
15            items[i], items[size - 1] = items[size - 1], items[i]
16
17
18for perm in generate_heaps(["A", "B", "C"]):
19    print(perm)

This version is often easier to integrate into other code because callers can iterate over the permutations one at a time.

Complexity and What "Efficient" Means Here

Any algorithm that outputs all permutations must deal with n! results, so the total work necessarily grows very quickly. Heap's algorithm does not avoid that combinatorial explosion.

A useful way to think about the complexity is:

• there are n! permutations
• producing each permutation involves at least some constant work, and often copying or outputting n elements

So the total time is typically described as O(n! * n) when you count the cost of emitting full permutations. The in-place swapping itself is efficient, but the output size dominates very quickly.

Space usage is better behaved. Aside from the recursion stack and the current array, the algorithm does not need an extra visited structure or large auxiliary storage.

When to Use Heap's Algorithm

Heap's algorithm is a good fit when:

• you need to generate every permutation
• you want an in-place recursive approach
• the input size is small enough that n! is still practical

It is not a good fit when you only need a count, a best permutation under some scoring rule, or a single random permutation. In those cases, generating all permutations is usually the wrong tool entirely.

Python's standard library already includes itertools.permutations, which is usually the practical choice in production Python code. Heap's algorithm is still worth learning because it explains one elegant way to enumerate permutations with controlled swapping.

Common Pitfalls

The most common mistake is forgetting that the algorithm mutates the list in place, which surprises callers that expect the original order to remain untouched. Another is appending the live list object directly instead of copying it, which causes every stored result to end up identical after later swaps. Developers also sometimes describe the runtime as merely O(n!) without acknowledging that outputting each permutation itself costs work. A final issue is using the algorithm on inputs that are too large, because permutation generation becomes infeasible very quickly.

Summary

• Heap's algorithm generates all permutations by recursively swapping elements in place.
• Its odd-even swap rule is what ensures complete coverage without duplicates.
• A generator version is often more useful than printing directly.
• The algorithm is memory-efficient, but total runtime still grows factorially with the number of items.
• Use it when you truly need every permutation, not when a smaller search or sampling problem would do.