A brief explanation of Heap's algorithm

Heap's algorithm (named after its inventor and not the data structure) generates all $N!$ permutations while only swapping two elements between successive permutations and requiring only $O(N)$ memory overhead and something like $O(1)$ amortized computation per step. It's not clear that this should even be possible. Unfortunately understanding how it works doesn't seem to lend any deep insights into the fundamental nature of computation. Also unfortunately the explanation presented here requires calculating permutation compositions represented in cycle notation and seeing that it works for all N requires doing these calculations.

CASE 1

The following is the pattern of swaps generated by Heap's algorithm for N=6.

(1 5)
        (1 6)
(1 5)
        (2 6)
(1 5)
        (3 6)
(1 5)     
        (4 6)
(1 5)    
        (5 6)
(1 5)         

1. Consider the first 3 swaps. These only involve elements 1, 5, 6. (Equivalent to (1)(5 6)).
2. Consider the final 3 swaps. These only involve elements 1, 5, 6. (Equivalent to (1 6)(5)).
3. Consider the middle swaps (all swaps not yet considered, from (2 6) to (4 6)). For these, the right column swaps will never interact with the left column swaps because they never have an element in common. The right column swaps will form a cycle and the left column will fix the 1 and 5. (1)(2 3 4 6)(5).
4. In total we have:

(1)(5 6) (1)(2 3 4 6)(5) (1 6)(5)

Direct calculation reveals this reduces to a cycle:

(1 6 5 2 3 4)

5. The general pattern for (even) N can be seen as:

(1)(N-1 N) (1)(2 3 4 5 ... N-2 N)(N-1) (1 N)(N-1)

which always reduces to

(1 N N-1 2 3 4 5 ... N-2)

in particular, a full cycle.

CASE 2

The following is the pattern of swaps generated by Heap's algorithm for N=5:

(1 4 3 2)
            (1 5)
(1 4 3 2)
            (1 5)
(1 4 3 2)
            (1 5)
(1 4 3 2)
            (1 5)
(1 4 3 2)

Direct calculation reveals this reduces to

(1 5)(2)(3)(4)

This is the general case for all (odd) N:

(1 N)(2)(3)...(N-1)

In other words only the first and last elements swap and the rest of the elements are fixed.

All together

From the point of view of an arbitrary index location K, Heap's algorithm alternates a prefix action with a specified sequence of pair swaps depending on the prefix action.

If the prefix action cycles the prefix as in case 2 above then the pair swaps are the (1 K), (1 K), ...,(1 K) sequence. This results in the prefix that includes K doing the head-tail swap.

If the prefix action is the head-tail swap then the pair swaps are (1 K), (2 K), (3 K),...,(K-1 K) as in case 1 above. This results in the prefix that includes K doing a full cycle.

We have to keep track of an $O(N)$ array and scan into it each step to know what index to swap.