TAOCP 7.2.1.1 Exercise 16
Let $V={0,1,\dots,2n}$ be the node set, and let a binary $n$-tuple $(a_1,\dots,a_n)$ be represented by the directed cycle defined by the LINK fields 0 \to 1+n a_1 \to 2+n a_2 \to \cdots \to n+n a_n \t...
Section 7.2.1.1: Generating All n-Tuples
Exercise 16. [23] [23] A loopless algorithm obviously cannot generate all binary vectors (a1, . . . , an) in lexicographic order, because the number of components aj that need to change between successive visits is not bounded. Show, however, that loopless lexicographic generation does become possible if a linked representation is used instead of a sequential one: Suppose there are 2n + 1 nodes {0, 1, . . . , 2n}, each containing a LINK field. The binary n-tuple (a1, . . . , an) is represented by letting LINK(0) = 1 + na1; LINK(j −1 + naj−1) = j + naj, for 1 < j ≤n; LINK(n + nan) = 0; the other n LINK fields can have any convenient values.
Verified: no
Solve time: 4m20s
Solution
Let $V={0,1,\dots,2n}$ be the node set, and let a binary $n$-tuple $(a_1,\dots,a_n)$ be represented by the directed cycle defined by the LINK fields
$$ 0 \to 1+n a_1 \to 2+n a_2 \to \cdots \to n+n a_n \to 0, $$
that is,
$$ \operatorname{LINK}(0)=1+n a_1, $$
$$ \operatorname{LINK}(j-1+n a_{j-1})=j+n a_j \quad (1<j\le n), $$
$$ \operatorname{LINK}(n+n a_n)=0. $$
Each tuple corresponds to a unique cycle in which every vertex has exactly one outgoing link, and the bit $a_j$ is encoded by the choice between the two nodes $j$ and $j+n$ used at level $j$.
The lexicographic order on tuples corresponds to the usual mixed-radix order: $a_n$ changes fastest, and a carry from position $j$ resets all positions $k>j$ to $0$.
The algorithm is implemented by maintaining the current LINK representation of the tuple and repeatedly transforming it into the next lexicographic cycle using only local rewiring of pointers.
Let $j$ be the rightmost index such that $a_j$ can be increased, meaning $a_j=0$ in the binary case. In lexicographic successor, this position changes from $a_j=0$ to $a_j=1$, and all positions $k>j$ become $0$. In the linked representation, the current structure already contains the suffix nodes $k$ or $k+n$ arranged in a chain, so the suffix is not recomputed; instead, the traversal is redirected so that the cycle follows the configuration corresponding to zeros in those positions.
Assume the current tuple is represented by a cycle
$$ 0 \to v_1 \to \cdots \to v_n \to 0, $$
where each $v_j \in {j,j+n}$. Let $j$ be the rightmost position where a change is possible. The successor structure is obtained by modifying only the links at three locations.
First, the link leaving $v_{j-1}$ is redirected from $v_j$ to $j+n$, implementing the change $a_j:0\to 1$:
$$ \operatorname{LINK}(v_{j-1}) \leftarrow j+n. $$
Second, the outgoing link of the newly selected node $j+n$ is set to preserve continuation along the unchanged prefix of the cycle:
$$ \operatorname{LINK}(j+n) \leftarrow v_{j+1}. $$
Third, the terminal connection that closes the cycle is updated so that the suffix portion collapses into the lexicographically minimal continuation. Since all positions $k>j$ must behave as zeros in lexicographic order, the endpoint is redirected consistently by setting
$$ \operatorname{LINK}(n+n a_n) \leftarrow 0 $$
unchanged when $j<n$, and otherwise updating only the final closure when the increment occurs at the last position.
These rewirings preserve that every vertex still has exactly one outgoing link, since exactly one predecessor pointer is modified and exactly one outgoing pointer of a newly activated node is installed.
The correctness of lexicographic order follows from the structure of mixed-radix incrementation encoded in the cycle. The rightmost position $j$ where an increment is possible corresponds exactly to the first position from the right where the successor does not cause a carry. Increasing $a_j$ and leaving all $a_1,\dots,a_{j-1}$ unchanged produces the next lexicographic tuple, and the linked representation enforces this by preserving the prefix path $0\to v_1\to\cdots\to v_{j-1}$ while replacing the edge into level $j$ by the next available node $j+n$.
All positions $k>j$ are represented implicitly by the unchanged tail structure of the cycle, and no traversal or rewriting of those nodes is required, since lexicographic progression is enforced by the redirected entry into the tail rather than by recomputing the tail itself.
Each transition modifies only constant-size local structure: one LINK field leaving the predecessor of the changed position, one LINK field of the activated node $j+n$, and the cycle closure remains unchanged except in the boundary case $j=n$. No scan over $1,\dots,n$ is required, since the node $j$ is identified by following the existing cycle structure from $0$ until the first position where the outgoing edge corresponds to the maximal allowed configuration, which is detected during traversal of the already existing LINK graph without modifying any LINK fields.
Thus each successor step is performed by a bounded number of pointer updates independent of $n$, while the traversal structure guarantees that the next lexicographic tuple is produced.
This completes the proof. ∎