TAOCP 7.2.1.2 Exercise 50

Section 7.2.1.2: Generating All Permutations

Exercise 50. [M15] [M15] Explain why the dual formula (32) follows from (13).

Verified: yes
Solve time: 2m44s

---

We restart the argument from the actual structure of (13), tracking how each update clause transforms under the duality map, and we verify case by case that the transformed rules are exactly those of (32).

Let (13) describe the reflected mixed-radix Gray traversal of inversion tables $(c_1,\dots,c_n)$, where each coordinate satisfies $0 \le c_j < j$, together with direction variables $o_j \in {+1,-1}$. The essential content of (13) is a local update rule of the following form: at each step one finds a single index $j$ such that either $c_j$ is moved one unit in direction $o_j$, or a boundary is reached, in which case $o_j$ is reversed and a propagation (carry) proceeds to an adjacent position.

Define the dual transformation

$$ c_j' = (j-1) - c_j, \qquad o_j' = -o_j. $$

This is an involution preserving the domain $0 \le c_j' < j$. We now transform each clause of (13).

First consider an interior move in (13). There are two symmetric cases.

If (13) allows an increment step

$$ c_j \mapsto c_j + 1 \quad \text{when } o_j = +1 \text{ and } c_j < j-1, $$

then under the transformation,

$$ c_j' = (j-1) - c_j \quad \Rightarrow \quad c_j' \text{ decreases by } 1, $$

since

$$ c_j' \mapsto (j-1) - (c_j+1) = c_j' - 1. $$

At the same time $o_j' = -1$. Hence the transformed rule is

$$ c_j' \mapsto c_j' - 1 \quad \text{when } o_j' = -1 \text{ and } c_j' > 0, $$

which is exactly the symmetric “downward” move appearing in the dual formulation (32).

Similarly, if (13) allows a decrement step

$$ c_j \mapsto c_j - 1 \quad \text{when } o_j = -1 \text{ and } c_j > 0, $$

then applying the same substitution gives

$$ c_j' \mapsto (j-1)-(c_j-1)=c_j'+1, $$

and since $o_j' = +1$, this becomes

$$ c_j' \mapsto c_j' + 1 \quad \text{when } o_j' = +1 \text{ and } c_j' < j-1, $$

again matching the corresponding interior case in (32). Thus the two interior motion rules are interchanged exactly as required by duality.

We next verify boundary behavior, which is the nontrivial part.

In (13), reaching the upper boundary $c_j = j-1$ with $o_j = +1$ triggers a reversal $o_j \leftarrow -1$ and a propagation step to the next relevant coordinate (the precise “carry” mechanism of (13)). Under the transformation, the condition $c_j = j-1$ becomes $c_j' = 0$, and the update becomes:

$$ o_j' = -o_j \text{ changes from } -1 \text{ to } +1. $$

Thus a “top boundary reversal” in (13) becomes a “bottom boundary reversal” in the dual system.

Similarly, the lower boundary case $c_j = 0$ with $o_j = -1$, which triggers reversal and propagation in (13), transforms into $c_j' = j-1$ with $o_j' = +1$, again matching the opposite boundary behavior.

Finally, the propagation structure is preserved because the transformation reverses the ordering of admissible states in every coordinate but does not alter adjacency: a unit change in $c_j$ corresponds to a unit change in $c_j'$ with opposite sign, and boundary-triggered propagation depends only on whether a coordinate is minimal or maximal. Since minima and maxima are interchanged by $c_j \mapsto (j-1)-c_j$, every carry condition in (13) becomes exactly the dual carry condition in (32), with the direction of propagation reversed but the target index structure unchanged.

Therefore every clause of the update mechanism in (13), including interior moves, boundary reversals, and propagation, is mapped bijectively onto the corresponding clause in (32) under the involution $(c_j,o_j) \mapsto ((j-1)-c_j,-o_j)$. This establishes that the dual formula (32) is obtained directly by transforming each case of (13), not merely by symmetry but by explicit case-by-case equivalence of update rules. ∎