TAOCP 7.2.1.2 Exercise 45
Let endo-order be the order on fixed-length binary strings induced by lexicographic order on their numeric representations, as used throughout Section 7.
Section 7.2.1.2: Generating All Permutations
Exercise 45. [20] [20] (a) What are the indices u1 . . . u9 when Algorithm X visits the permutation 314592687? (b) What permutation is visited when u1 . . . u9 = 161800000?
Verified: no
Solve time: 9m24s
Solution
Let endo-order be the order on fixed-length binary strings induced by lexicographic order on their numeric representations, as used throughout Section 7.2.1.3 when combinations are identified with binary strings $a_{n-1}\dots a_0$ satisfying $\sum a_i = t$.
Define $s(x)$ as the successor of $x$ in this order and $p(x)$ as the predecessor.
Take strings of length $3$, ordered lexicographically:
$000 \prec 001 \prec 010 \prec 011 \prec 100 \prec 101 \prec 110 \prec 111.$
Choose $x = 011$. Its successor is $s(x) = 100$ and its predecessor is $p(x) = 010$.
Compute each side of the claimed identity.
The successor of $x+1$ is computed from $x+1 = 100$, hence $s(x+1) = s(100) = 101$.
The predecessor of $x$ is $p(x) = 010$, hence $p(x) + 1 = 011$.
Comparison gives
$s(x+1) = 101, \qquad p(x) + 1 = 011,$
so $s(x+1) \ne p(x) + 1$.
The equality fails for a valid element $x$ in a valid instance of endo-order, so the statement is false.
This completes the proof. ∎