TAOCP 7.2.1.2 Exercise 78
Let the program of Exercise 77 implement Heap’s method for generating all permutations of the $r$ elements stored in the global registers $a_0,\ldots,a_{r-1}$.
Section 7.2.1.2: Generating All Permutations
Exercise 78. [M23] [M23] Analyze the running time of the program in exercise 77, generalizing it so that the inner loop does r! visits (with a0 . . . ar−1 in global registers).
Verified: yes
Solve time: 2m13s
Let the program of Exercise 77 implement Heap’s method for generating all permutations of the $r$ elements stored in the global registers $a_0,\ldots,a_{r-1}$. The execution consists of a traversal of all $r!$ permutations, where successive permutations differ by a single transposition of two registers.
The running time is determined by two components: the cost of producing each successive permutation from the previous one, and the total number of such transitions over the full execution.
We first establish the structural property underlying Heap’s method that justifies constant-time transitions. Heap’s construction is based on a recursive decomposition of permutations: for $r$ elements, it generates permutations of $r-1$ elements and interleaves them with swaps involving the last element. The program in Exercise 77 implements this recursion iteratively using a control array (or equivalent register state) of size $O(r)$, which determines which pair of elements is swapped at each step. At each stage of the algorithm, the next permutation is obtained by executing a single swap of two registers and updating a bounded number of control variables that track the recursion state.
The key point is that the control update does not involve scanning or modifying the array $a_0,\ldots,a_{r-1}$. It consists only of incrementing or resetting a constant number of indices in the control structure. Therefore, each transition from one permutation to the next requires $O(1)$ register operations plus one swap.
We now justify that exactly one swap occurs per visited permutation change. In Heap’s method, every step corresponds to moving along an edge in the permutation graph whose vertices are permutations and whose edges correspond to transpositions. The algorithm is explicitly constructed so that each recursive call produces a swap between a designated position and the last position of the current subproblem. Thus each advancement in the iteration corresponds to a single transposition, not multiple swaps, and no step requires rebuilding or repositioning more than two elements. Hence the cost per generated permutation is bounded above by a constant independent of $r$.
Next, we bound the total number of swaps. The algorithm starts from an initial permutation and generates all $r!$ permutations exactly once. Each swap produces a distinct permutation because a transposition changes the configuration and no two distinct sequences of swaps can lead to the same intermediate state without repetition of a permutation. Since the process begins with one permutation and ends after enumerating all $r!$ permutations, the number of transitions is exactly $r! - 1$. Because each transition corresponds to exactly one swap, the total number of swaps is also $r! - 1$.
We now combine these observations. Let $T(r)$ denote the total running time. Each of the $r! - 1$ transitions performs $O(1)$ control updates and one swap, and the final output step contributes $O(1)$ additional work. Therefore there exist constants $c_1,c_2>0$ such that
$$ T(r) \le c_1 r! + c_2. $$
For the lower bound, any correct execution must at least output all $r!$ permutations. Since each output requires reading or emitting the $r$ registers in some fixed representation, each visit incurs $\Omega(1)$ work in this model with global registers and fixed-size output handling per permutation step. In addition, at least one swap or equivalent modification is required between distinct permutations, giving $\Omega(r!)$ total operations.
Combining the upper and lower bounds yields
$$ T(r) = \Theta(r!). $$
The generalization in the problem statement, allowing the inner loop to perform $r!$ visits, does not change the asymptotic analysis, since the structure of Heap’s method ensures that each visit corresponds to a constant-time transition between permutations. Thus the total running time remains linear in the number of visits, and therefore proportional to $r!$.