TAOCP 7.2.1.2 Exercise 14
The statement claims an invariant relation in Algorithm P: at the beginning of step P5, $a_{j-c_j+s} = x_j$ for all $j$, where $x_1x_2\cdots x_n$ is the initial permutation and $c_1\cdots c_n$, $s$ ar...
Section 7.2.1.2: Generating All Permutations
Exercise 14. [M22] [M22] True or false: If a1a2 . . . an is initially x1x2 . . . xn in Algorithm P, we always have aj−cj+s = xj at the beginning of step P5.
346 COMBINATORIAL SEARCHING 7.2.1.2
Verified: no
Solve time: 7m28s
Solution
The statement claims an invariant relation in Algorithm P:
at the beginning of step P5,
$a_{j-c_j+s} = x_j$
for all $j$, where $x_1x_2\cdots x_n$ is the initial permutation and $c_1\cdots c_n$, $s$ are the current auxiliary variables.
The claim is evaluated at the moment just before executing the interchange in P5, i.e., after P4 has identified a valid index $j$ and after the corresponding updates of $j$ and $s$ in P3–P4–P6–P7.
The assertion would imply that every entry $a_k$ at that moment can be traced back to a fixed initial position $x_j$ using the formula $k=j-c_j+s$, independent of the history of previous exchanges.
The structure of Algorithm P shows that this is incompatible with how elements propagate through adjacent interchanges.
Consider first the effect of a single execution of P5. The interchange
$a_{j-c_j+s} \leftrightarrow a_{j-q+s}$
moves two elements, and each such element subsequently participates in further interchanges at different indices determined by later values of $(c_j,s)$ and by later choices of $j$. Hence the location of a given initial element $x_r$ depends on the entire sequence of previous values of $j$ and on all prior updates of $c_j$ and $s$.
To test the claimed identity, it suffices to track a concrete contradiction already at small $n$, since the statement is universal in $n$ and in all intermediate states.
Take $n=3$ with initial permutation $x_1x_2x_3=123$.
Initially $c_1=c_2=c_3=0$, $s=0$, $a_i=x_i$. The first application of P5 occurs at $j=3$, since $q=c_3+o_3=1$ and $q<j$. The interchange is
$a_{3-0+0} \leftrightarrow a_{3-1+0},$
so $a_3 \leftrightarrow a_2$, producing the permutation $132$.
At the next stage where P5 is executed again, the algorithm modifies $c_3$ and continues updating $j$ and $s$. The value of $s$ changes due to P6 whenever a boundary condition is reached, and the index $j-c_j+s$ is no longer aligned with the original labeling of positions in $x_1x_2x_3$.
At this point the claimed identity would require that, at the next occurrence of P5 involving some index $j=2$, we still have
$a_{2-c_2+s}=x_2=2.$
However, after the first interchange, the element $2$ has moved to position $3$, so $a_3=2$. The quantity $2-c_2+s$ equals $2$ at that moment because $c_2=0$ and $s$ has not yet increased, hence the formula would assert $a_2=2$, contradicting the actual configuration $132$.
The failure arises structurally because the index expression $j-c_j+s$ is tied to the inversion table representation, not to a fixed mapping between current array positions and initial labels. The variable $s$ counts indices $k>j$ with $c_k=k-1$, and this quantity changes when direction switches in P7 occur at higher indices. These changes alter the effective displacement of elements without preserving a fixed affine relation between current position and initial position.
Therefore the claimed equality cannot hold at all executions of P5, since the location of an initial element is not determined solely by $(j,c_j,s)$ at the moment of exchange.
The statement is false. ∎