TAOCP 7.2.1.2 Exercise 60

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: 6m39s

Solution

Let the vertex set be the symmetric group $S_n$, and let $\alpha_1,\dots,\alpha_{n-1}$ denote the adjacent transpositions used in Section 7.2.1.2.

Define two directed Cayley graphs:

In the first convention, there is an arc

$\pi \to \pi \alpha_j.$

In the second convention, there is an arc

$\pi \to \alpha_j \pi.$

To compare them, define a mapping $\varphi : S_n \to S_n$ by

$\varphi(\pi) = \pi^{-1}.$

This map is a bijection on $S_n$ since inversion is an involution.

Consider an arc in the first graph, $\pi \to \pi \alpha_j$. Applying $\varphi$ to both endpoints gives

$\varphi(\pi) = \pi^{-1},$

$\varphi(\pi \alpha_j) = (\pi \alpha_j)^{-1} = \alpha_j^{-1} \pi^{-1}.$

Since $\alpha_j$ is a transposition, $\alpha_j^{-1} = \alpha_j$, hence

$\varphi(\pi \alpha_j) = \alpha_j \pi^{-1}.$

Thus the image of an arc $\pi \to \pi \alpha_j$ is an arc

$\pi^{-1} \to \alpha_j \pi^{-1},$

which is exactly of the second type.

The same calculation reverses, so every arc of the second graph corresponds uniquely to an arc of the first under $\varphi$.

Therefore $\varphi$ is a graph isomorphism between the two Cayley graphs, and the two definitions differ only by relabeling of vertices via inversion.

This completes the proof. ∎