Introduction

Heap's algorithm is a classic way to generate permutations by swapping elements in place. If you are seeing a "mystery comma" while implementing it, that usually comes from output formatting or accidentally creating a tuple, not from the algorithm itself.

Heap's algorithm in one sentence

Heap's algorithm generates all permutations of an array by recursively generating permutations of the first n - 1 elements and then swapping elements according to whether n is odd or even.

A clean Python implementation looks like this:

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

This prints each permutation exactly once, and it does so by mutating the same list through controlled swaps.

Why the swap rule changes for odd and even n

This is the heart of Heap's algorithm:

• if n is odd, swap the first element with the last
• if n is even, swap the current loop element with the last

That pattern is what guarantees every permutation appears without needing a separate visited set or lexicographic next-permutation logic.

You do not need to memorize the proof for everyday use, but you do need to preserve that exact swap rule. Most incorrect implementations break the odd/even swap logic and then silently generate duplicates or miss permutations.

The "mystery comma" is usually a Python issue

When people mention a mysterious comma, it is often one of these problems.

1. Accidentally creating a tuple

In Python, a trailing comma can create a tuple:

value = [1, 2, 3],
print(value)

Output:

([1, 2, 3],)

That comma is not part of Heap's algorithm. It is Python tuple syntax.

2. Printing with old Python 2 habits

Older code sometimes used print syntax that behaves differently, which can make output look odd when copied into modern Python discussions.

3. Returning tuples instead of lists by accident

If you build permutations using expressions with commas rather than explicit list copies, the output may appear with tuple punctuation even though the algorithm was intended to work with lists.

A generator version is often cleaner

Instead of printing directly, you can yield permutations:

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

This separates generation from output formatting, which also makes mystery-comma bugs easier to isolate. If the generator yields lists but your final output shows tuples, the formatting layer is where the problem lives.

Complexity and practical use

Any algorithm that generates all permutations must deal with n! outputs, so the total time is necessarily proportional to the number of generated permutations.

Heap's algorithm is attractive because:

• it is in-place
• it uses simple swaps
• it avoids extra bookkeeping structures

That makes it a good teaching algorithm and a good choice when you explicitly want all permutations in memory-efficient recursive form.

Common Pitfalls

The biggest mistake is changing the odd/even swap rule. That breaks the algorithm even if the recursion still "looks right."

Another common issue is forgetting to copy the list before yielding or printing when you need a stable snapshot of the current permutation.

People also blame Heap's algorithm for output commas that are actually caused by tuple syntax or accidental formatting choices elsewhere in the code.

Finally, remember that permutation generation grows factorially. Even a correct implementation becomes expensive quickly as n increases.

Summary

• Heap's algorithm generates permutations by recursive in-place swapping.
• The odd/even swap rule is the key to the algorithm's correctness.
• A mystery comma in the output is usually a Python tuple or formatting issue, not an algorithm rule.
• A generator version often makes debugging and reuse easier.
• The algorithm is elegant, but permutation generation still scales as n!.