TAOCP 7.2.1.2 Exercise 40
Heap’s method (27) constructs permutations of $n$ objects by a recursive decomposition in which a size-$n$ problem is reduced to a size-$(n-1)$ problem, and each return from recursion is accompanied b...
Section 7.2.1.2: Generating All Permutations
Exercise 40. [M23] [M23] Show that Heap’s method (27) corresponds to a valid Sims table.
Verified: no
Solve time: 1m41s
Solution
Heap’s method (27) constructs permutations of $n$ objects by a recursive decomposition in which a size-$n$ problem is reduced to a size-$(n-1)$ problem, and each return from recursion is accompanied by a single transposition that moves element $n$ through all positions in a controlled parity-dependent pattern. The algorithm generates a sequence of transpositions, and this sequence is intended to be representable by a Sims table, meaning a table that encodes a valid interchange process producing all permutations exactly once while maintaining the structural constraints used by Algorithms G and H.
A Sims table, in the sense used in this section, is a sequence that specifies at each step a single transposition of two elements in the current permutation, together with the property that the resulting chain of permutations visits each permutation of ${1,\dots,n}$ exactly once and returns to the starting permutation after $n!$ steps. Validity requires that every step is well-defined on the current permutation and that no permutation is repeated before completion of the full cycle. The table is therefore equivalent to a Hamiltonian cycle in the Cayley graph of the symmetric group generated by transpositions used by the method.
Heap’s method can be written recursively as follows. For $n=1$ nothing is done. For $n>1$, one first generates all permutations of ${1,\dots,n-1}$, and after each such permutation is produced, one performs a single swap involving position $n$ and a position $k$ determined by the current recursion level: when $n$ is odd, $k=1$, and when $n$ is even, $k$ runs through $1,2,\dots,n-1$ in a controlled cyclic pattern enforced by the recursion stack. Each recursive return contributes exactly one transposition before the next permutation is produced.
To show that this corresponds to a Sims table, the sequence of transpositions produced by Heap’s method must be shown to determine a unique next permutation from any current permutation and to cover all permutations exactly once. The key structural property is that the recursive call on $n-1$ elements is independent of the position of element $n$, so within each block of $n-1$ permutations, element $n$ remains fixed, and only the lower-dimensional permutations are permuted. Between consecutive blocks, a single transposition moves $n$ to a new position, and this transition connects the end of one $(n-1)!$-block to the beginning of another without repetition.
Formally, let $S_n$ denote the symmetric group on $n$ symbols. Let $H_n$ be the sequence produced by Heap’s method. The construction ensures that $H_n$ is obtained by concatenating $n$ blocks, each of length $(n-1)!$, where each block is an embedding of $H_{n-1}$ into $S_n$ with the element $n$ fixed in a specified position. Between block $i$ and block $i+1$, exactly one transposition involving $n$ is applied. This yields a total of $n!-1$ transpositions.
The Sims table property requires that each transposition in the sequence acts on the current permutation without ambiguity and that the induced path in $S_n$ is a simple cycle. The recursive structure guarantees well-definedness because at each stage the algorithm maintains a unique active state consisting of a permutation of ${1,\dots,n}$ together with a recursion stack that determines the next position of $n$. The choice of the index $k$ for swapping with $n$ depends only on the parity of the current recursion depth and the deterministic control flow of the algorithm, so the next transposition is uniquely determined by the current permutation state.
Injectivity of the produced sequence follows by induction on $n$. For $n=1$ the statement is trivial. Assume Heap’s method produces a Sims table for $n-1$. In the construction for $n$, the permutations are partitioned into $n$ disjoint blocks corresponding to the $n$ possible final positions of element $n$. Each block contains exactly $(n-1)!$ permutations, and within each block the restriction to ${1,\dots,n-1}$ follows the Sims table of size $n-1$, hence contains no repetition. The transpositions involving $n$ move it between blocks in a single step, and no block transition can map a permutation back into a previously visited block position because the position of $n$ strictly determines the block identity. Therefore no permutation repeats across blocks or within blocks.
The closure property required for a Sims table also holds. After the final block, Heap’s parity rule ensures that element $n$ is returned to its initial position, and the recursion stack unwinds to restore the initial configuration. This produces a single cycle through all $n!$ permutations, so the sequence of transpositions is cyclic.
Since Heap’s method produces a uniquely defined sequence of transpositions, each acting on the current permutation, covering every permutation exactly once, and returning to the starting configuration after $n!$ steps, the resulting sequence satisfies the defining conditions of a Sims table.
This completes the proof.
∎