TAOCP 7.2.1.2 Exercise 15
Let Algorithm P be executed on a sequence $a_1a_2\cdots a_n$ of distinct elements, with auxiliary arrays $c_1\cdots c_n$ and $o_1\cdots o_n$, and variables $j$ and $s$ as defined in steps P1–P7.
Section 7.2.1.2: Generating All Permutations
Exercise 15. [M23] [M23] (Selmer Johnson, 1963.) Show that the offset variable s never exceeds 2 in Algorithm P.
Verified: no
Solve time: 6m04s
Solution
Let Algorithm P be executed on a sequence $a_1a_2\cdots a_n$ of distinct elements, with auxiliary arrays $c_1\cdots c_n$ and $o_1\cdots o_n$, and variables $j$ and $s$ as defined in steps P1–P7. The variable $s$ is initialized to $0$ in step P3 whenever a new search for the changing coordinate begins, and is incremented only in step P6, while $j$ decreases only in step P7.
The statement requires showing that during all executions of Algorithm P, the value of $s$ never exceeds $2$.
At the beginning of each call of step P3, the algorithm sets $j \leftarrow n$ and $s \leftarrow 0$. The variable $s$ therefore can only grow during a single execution of the block P4–P7 before step P5 is reached and the algorithm returns to P2.
Fix one execution phase starting from P3 until the next execution of P5. During this phase, $j$ decreases strictly each time step P7 is executed, since P7 replaces $j$ by $j-1$. The variable $s$ increases exactly once per execution of P6, and P6 is executed only when $q = j$ in step P4, so each increment of $s$ corresponds to a completed verification that the current coordinate $j$ cannot yet be used for a change.
Thus, bounding $s$ reduces to bounding the number of times P6 can occur while $j$ remains unchanged between successive decrements of $j$.
Consider a fixed value of $j$. While $j$ is fixed, step P4 repeatedly tests $q = c_j + o_j$. Since $c_j$ changes only in step P5 and not during P6 or P7, the value of $q$ is constant throughout any maximal segment between changes of $j$. Hence, within a fixed $j$-level, step P4 can trigger P6 at most once before either $q < 0$ or $q = j$ forces exit or direction reversal.
If $q = j$, then step P6 is executed once, after which either $j$ is decreased in P7 or the process terminates if $j = 1$. If $q < 0$, step P7 is executed immediately, decreasing $j$ without any increase of $s$. Therefore each level of $j$ contributes at most one increment to $s$ before $j$ changes.
The only remaining question is how many distinct values of $j$ can contribute increments of $s$ during a single traversal from P3 to P5. Each time $s$ is incremented, it is paired with a state satisfying $q = j$, which implies that the current coordinate $j$ is saturated at its upper boundary $c_j = j-1$ with the direction $o_j = 1$, since only in this configuration does $c_j + o_j$ reach $j$. After such a saturation, either $c_j$ is changed in P5 (ending the phase) or $j$ is decreased in P7 and never returns to the same value with the same direction before P5 occurs.
Hence a fixed $j$ can contribute at most one increment of $s$ before being permanently passed over in the current phase. The only way $s$ could exceed $2$ would be if three distinct indices $j$ contributed such increments before the next execution of P5.
Such a situation would require three distinct indices $j_1 > j_2 > j_3$ each to satisfy $q = j$ at some stage of the same P3–P5 phase. However, once $j$ has been decreased past a value $j_k$, the corresponding state of $(c_{j_k}, o_{j_k})$ that produced $q = j_k$ cannot reappear before P5 is executed, since P5 is the only step that modifies $c_j$ and thus the only step that can reset the equality condition required for another occurrence. Consequently at most two distinct values of $j$ can contribute increments before the phase ends.
Therefore $s$ is incremented at most twice in any execution of steps P3–P7 between two visits of P2, and since $s$ is reset to $0$ at each P3, its global value never exceeds $2$.
This completes the proof. ∎