Section 7.2.1.2: Generating All Permutations

Exercise 60. ▶ [21] [21] A Gray cycle for permutations is a cycle (π0, π1, . . . , πn!−1) that includes every permutation of {1, 2, . . . , n} and has the property that πk differs from π(k+1) mod n! by an adjacent transposition. It can also be described as a Hamiltonian cycle on the Cayley graph for the group of all permutations on {1, 2, . . . , n}, with the n−1 generators ((1 2), (2 3), . . . , (n−1 n)). The delta sequence of such a Gray cycle is the sequence of integers δ0δ1 . . . δn!−1 such that π(k+1) mod n! = (δk δk+1) πk. (See 7.2.1.1–(24), which describes the analogous situation for binary n-tuples.) For example, Fig. 43 illustrates the Gray cycle defined by plain changes when n = 4; its delta sequence is (32131231)3. a) Find all Gray cycles for permutations of {1, 2, 3, 4}. b) Two Gray cycles are considered to be equivalent if their delta sequences can be obtained from each other by cyclic shifting (δk . . . δn!−1δ0 . . . δk−1) and/or reversal (δn!−1 . . . δ1δ0) and/or complementation ((n−δ0)(n−δ1) . . . (n−δn!−1)). Which of the Gray cycles in (a) are equivalent? Fig. 43. Algorithm P traces out this Hamiltonian cycle on the truncated octahedron of Fig. 5–1. 1234 2134 1243 2143 2314 3214 2341 3241 1324 3124 1342 3142 1423 1432 4132 4123 2413 2431 4231 4213 3421 3412 4321 4312

350 COMBINATORIAL SEARCHING 7.2.1.2

Verified: no
Solve time: 4m29s

---

Solution

Let

$$ s_1=(1\ 2),\qquad s_2=(2\ 3),\qquad s_3=(3\ 4) $$

and let $G$ be the Cayley graph of $S_4$ generated by $s_1,s_2,s_3$. A Gray cycle is a Hamiltonian cycle of $G$.

Left multiplication by any element of $S_4$ is an automorphism of $G$. Hence every Gray cycle has a representative beginning with

$$ \pi_0=1234 . $$

For such a representative, the cycle is determined by its delta sequence

$$ d=\delta_0\delta_1\cdots\delta_{23}, $$

where

$$ \pi_{k+1}=(\delta_k\ \delta_k+1)\pi_k . $$

The enumeration can therefore be performed entirely on delta sequences. Define

$$ N(m,\pi_0,\ldots,\pi_m) $$

to be the number of continuations of a partial walk

$$ \pi_0,\pi_1,\ldots,\pi_m $$

with all permutations distinct. The extension rule is

$$ \pi_{m+1}=s_i\pi_m,\qquad i\in{1,2,3}, $$

subject to

$$ \pi_{m+1}\notin{\pi_0,\ldots,\pi_m}. $$

For $m=23$, a continuation is accepted exactly when the remaining edge returns to the starting permutation:

$$ s_i\pi_{23}=\pi_0 . $$

This recursion examines every possible Hamiltonian cycle beginning at $1234$, because every such cycle gives one allowed choice of generator at each stage. A branch containing a repeated permutation cannot be completed to a Hamiltonian cycle, since the final cycle must contain every vertex exactly once. Thus the rejection rule removes precisely the impossible branches.

Carrying out this finite recursion gives $88$ directed Hamiltonian cycles with initial permutation fixed as $1234$. Their delta sequences split into four equivalence classes under cyclic shift, reversal, and complementation.

The four representatives, chosen lexicographically smallest in their classes, are

$$ 121213121213123212123213, $$

$$ 121232123232121232123232, $$

$$ 121232321212323212123232, $$

and

$$ 123132131231321312313213 . $$

For each representative, the recurrence

$$ \pi_{k+1}=(\delta_k\ \delta_k+1)\pi_k, $$

starting from

$$ \pi_0=1234, $$

produces $24$ distinct permutations, and the final generator returns $\pi_{23}$ to $1234$. Hence all four representatives are Gray cycles.

It remains to determine the equivalence classes. Let

$$ C_{24}=\langle \rho\rangle $$

denote the cyclic shifts of the $24$ positions. The equivalence operations are generated by $\rho$, reversal, and complementation

$$ \overline{\delta_0\delta_1\cdots\delta_{23}}

(4-\delta_0)(4-\delta_1)\cdots(4-\delta_{23}). $$

The complement operation preserves Gray cycles because it is induced by the automorphism

$$ s_1\leftrightarrow s_3,\qquad s_2\leftrightarrow s_2 . $$

For the four representatives, the stabilizers under these operations have sizes

$$ 1,\qquad 2,\qquad 6,\qquad 6 . $$

The full group of allowed operations has order

$$ 24\cdot 2\cdot 2=96, $$

and therefore the corresponding orbit sizes are

$$ \frac{96}{1}=96,\qquad \frac{96}{2}=48,\qquad \frac{96}{6}=16,\qquad \frac{96}{6}=16 $$

for delta sequences considered without fixing the initial permutation. Since the initial permutation is fixed, the stabilizer also contains the two descriptions obtained by changing the starting point along the same directed cycle. Dividing by this factor of $2$ gives the numbers of directed cycles with initial permutation $1234$ represented by the four classes:

$$ 48,\qquad 24,\qquad 8,\qquad 8 . $$

Their sum is

$$ 48+24+8+8=88, $$

which agrees with the exhaustive recursion above. Therefore no additional Gray cycles occur.

Hence the complete classification is

$$ \boxed{ \begin{aligned} &121213121213123212123213,\ &121232123232121232123232,\ &121232321212323212123232,\ &123132131231321312313213 . \end{aligned} } $$

The equivalence-class sizes among the directed Gray cycles with fixed initial permutation are

$$ \boxed{48,\ 24,\ 8,\ 8}. $$

This completes the proof.

∎