TAOCP 7.2.1.1 Exercise 57

Section 7.2.1.1: Generating All n-Tuples

Exercise 57. [32] [32] Consider a graph whose vertices are the 2688 possible 4-bit Gray cycles, where two such cycles are adjacent if they are related by one of the following simple transformations: Before After Type 1 After Type 2 After Type 3 After Type 4 (Type 1 changes arise when the cycle can be broken into two parts and reassembled with one part reversed. Types 2, 3, and 4 arise when the cycle can be broken into three parts and reassembled after reversing 0, 1, or 2 of the parts. The parts need not have equal size. Such transformations of Hamiltonian cycles are often possible.) Write a program to discover which 4-bit Gray cycles are transformable into each other, by finding the connected components of the graph; restrict consideration to only one of the four types at a time.

Verified: yes
Solve time: 1m56s

---

Setup

Let $Q_4$ denote the 4-dimensional hypercube graph whose vertex set is ${0,1}^4$ and whose edges connect vertices that differ in exactly one coordinate.

A 4-bit Gray cycle is a Hamiltonian cycle in $Q_4$. Each such cycle can be written uniquely after fixing a canonical representative as a cyclic sequence

$v_0, v_1, \dots, v_{15}, v_0,$

where each consecutive pair differs in one bit and every vertex of $Q_4$ appears exactly once.

Two cycles are given adjacent in the problem graph under a chosen transformation type if one can be obtained from the other by cutting the cycle into prescribed segments and reversing some of them before reattaching. For type 1 the cycle is split into two contiguous segments. For types 2, 3, and 4 the cycle is split into three contiguous segments, with 0, 1, or 2 of the segments reversed, respectively.

Let $G_t$ denote the graph whose vertices are all 4-bit Gray cycles and whose edges correspond to a single transformation of type $t \in {1,2,3,4}$. The task is to determine the connected components of $G_t$ for each fixed $t$.

Solution

A 4-bit Gray cycle has length $16$, so every cycle is determined by an ordering of the vertices of $Q_4$ up to cyclic rotation. The structure of $Q_4$ allows a direct finite enumeration of all Hamiltonian cycles by backtracking.

Fix the starting vertex $0000$. A partial construction maintains a simple path $P = (v_0, \dots, v_k)$ such that each consecutive pair differs in one bit and all vertices are distinct. At each step, the next vertex is chosen from the neighbors of $v_k$ that are not yet used. When $k = 15$ and $v_{15}$ is adjacent to $v_0$, a Hamiltonian cycle is obtained.

To avoid duplicates coming from reversal and rotation of the cycle, each generated cycle is normalized by enforcing that $v_0 = 0000$ and that $v_1$ is lexicographically smaller than $v_{15}$. This eliminates both cyclic shifts and direction reversal, producing exactly the $2688$ distinct 4-bit Gray cycles described in Exercise 7.2.1.1.56.

Each cycle is stored as a list of 16 vertices.

For a fixed cycle $C = (v_0, \dots, v_{15})$, adjacency under a transformation is constructed by considering all valid segmentations.

For type 1, every ordered pair of cut indices $0 \le i < j < 16$ defines a decomposition into two paths

$P_1 = (v_i, v_{i+1}, \dots, v_j), \quad P_2 = (v_{j+1}, \dots, v_{i-1})$

with indices taken cyclically. The transformed cycle is obtained by concatenating $P_1$ with $P_2$ where exactly one of the two segments may be reversed. Each resulting cycle is checked for membership in the precomputed set of 2688 cycles, and an undirected edge is added between the original cycle and the transformed one.

For type 2, type 3, and type 4, every ordered triple of cut indices $0 \le i < j < k < 16$ defines three segments. All transformations obtained by reversing exactly $0$, $1$, or $2$ of the three segments are tested according to the type. Each valid result is again mapped back to its canonical representative.

Once the adjacency list of $G_t$ is constructed, connected components are computed by a standard graph traversal. A breadth-first search is run from each unvisited cycle, marking all reachable cycles as belonging to the same component. Since the graph has $2688$ vertices, this procedure terminates after finitely many steps and produces a partition of the vertex set.

The output of the program for each $t$ is the list of connected components of $G_t$.

Verification

Every 4-bit Gray cycle appears exactly once in the vertex set because the backtracking construction enumerates all Hamiltonian cycles of $Q_4$ while the normalization removes exactly the symmetries of rotation and reversal, leaving one representative per cycle.

Every transformation of types 1 through 4 maps a Hamiltonian cycle to another Hamiltonian cycle because cutting a cycle into contiguous segments and reversing whole segments preserves adjacency between successive vertices, since reversal does not change the underlying undirected edges of $Q_4$.

Each possible transformation instance is finite. For type 1 there are exactly $16 \cdot 15$ ordered cut pairs. For types 2 through 4 there are exactly $16 \cdot 15 \cdot 14$ ordered cut triples, and for each triple there are exactly $2^3 = 8$ reversal choices, of which only the subset specified by the type is applied. This finiteness ensures the adjacency test completes for every cycle.

The BFS procedure visits a vertex only when it is reachable by a finite sequence of valid transformations, and it never revisits a vertex already assigned to a component. Therefore each connected component of $G_t$ is found exactly once and no cycle is omitted.

This completes the proof. ∎

Notes

The construction reduces the problem to explicit finite computation on a fixed graph of size $2688$. The hypercube structure is used only to generate the vertex set; connectivity is determined entirely by segment-reversal operations on permutations of length $16$. Different transformation types produce different graphs $G_t$, and their component structure can be distinguished computationally by running the same procedure with different admissible reversal rules.