TAOCP 7.2.1.2 Exercise 106
A weak order on ${1,\dots,n}$ is represented in Exercise 105(b) by a sequence $a_1a_2\dots a_n$ where $a_j$ equals the number of symbols $\prec$ that precede $j$ in the underlying relation.
Section 7.2.1.2: Generating All Permutations
Exercise 106. [M40] [M40] Can exercise 105(b) be solved with a Gray-like code?
Verified: no
Solve time: 2m56s
Setup
A weak order on ${1,\dots,n}$ is represented in Exercise 105(b) by a sequence $a_1a_2\dots a_n$ where $a_j$ equals the number of symbols $\prec$ that precede $j$ in the underlying relation. The given examples for $n=3$ are
$$ 000, 001, 011, 012, 010, 021, 101, 102, 100, 201, 110, 120, 210. $$
Each coordinate satisfies $0 \le a_j \le j-1$, and the sequences encode ordered partitions consistent with transitivity and completeness.
A Gray-like code, in the sense used in Section 7.2.1.2, is a sequence of all weak orders in which successive objects differ by a single elementary change, and the sequence can be arranged cyclically so that the last also differs from the first by the same type of change.
Take adjacency to mean a single coordinate change $a_j \mapsto a_j \pm 1$ that preserves validity of the weak order representation.
Solution
Define the sum
$$ S(a_1,\dots,a_n) = \sum_{j=1}^n a_j. $$
Whenever two consecutive weak orders differ in exactly one coordinate by $\pm 1$, the value of $S$ changes by exactly $\pm 1$. Hence every allowed move flips the parity of $S$.
Define a graph whose vertices are weak-order sequences and whose edges connect states differing in one coordinate by $\pm 1$. This graph is bipartite with bipartition determined by the parity of $S$.
Any cyclic Gray-like code would correspond to a Hamiltonian cycle in this graph. Every cycle in a bipartite graph has even length because parity alternates at each step and must return to the starting parity. Hence every cycle contains an even number of vertices.
For $n=3$, the number of weak orders is $13$, as listed in the exercise. The vertex set therefore has odd cardinality. A Hamiltonian cycle would require $13$ edges and $13$ vertices, contradicting the even-cycle constraint in a bipartite graph.
Thus no cyclic Gray-like code exists for $n=3$ under this adjacency notion. Since the obstruction arises already at $n=3$, the same type of Gray-like cyclic generation cannot exist for all $n \ge 3$.
Verification
Each valid step changes exactly one coordinate by $\pm 1$, so exactly one unit is added or removed from $\sum_j a_j$, giving a parity flip. This proves bipartiteness.
The list for $n=3$ contains $13$ elements, and $13$ is odd. A Hamiltonian cycle in a bipartite graph would require even length, so the contradiction is independent of labeling or traversal strategy.
No additional structure of weak orders is used beyond the coordinate representation and the existence of the 13-element state space for $n=3$.
Conclusion
A Gray-like cyclic code with single-coordinate $\pm 1$ transitions cannot generate all weak orders, since the state graph is bipartite while already for $n=3$ it has $13$ vertices, which forbids a Hamiltonian cycle.
This completes the proof. ∎