TAOCP 7.2.1.2 Exercise 20

Section 7.2.1.2: Generating All Permutations

Exercise 20. ▶ [20] [20] The n-cube has 2nn! symmetries, one for each way to permute and/or com- plement the coordinates. Such a symmetry is conveniently represented as a signed permutation, namely a permutation with optional signs attached to the elements. For example, 231 is a signed permutation that transforms the vertices of the 3-cube by changing x1x2x3 to x2x3x1, so that 000 → 001, 001 → 011, . . . , 111 → 110. Design a simple algorithm that generates all signed permutations of {1, 2, . . . , n}, where each step either interchanges two adjacent elements or negates the first element.

Verified: no
Solve time: 5m05s

We construct an explicit Hamiltonian path on the Cayley graph of the hyperoctahedral group $B_n$, whose vertices are signed permutations of ${1,\dots,n}$. A vertex is a sequence $(a_1,\dots,a_n)$ where $(|a_1|,\dots,|a_n|)$ is a permutation of ${1,\dots,n}$, and each $a_i$ has a sign.

The allowed moves are exactly the generators $s_i$ for $1 \le i < n$, which swap positions $i$ and $i+1$, and $t$, which negates the first element. We must produce a sequence that visits every vertex exactly once.

The key idea is to separate two mechanisms that interact cleanly: an underlying Johnson–Trotter traversal of permutations using adjacent swaps, and a controlled rule that flips signs only when an element passes through the first position. No global Gray code over sign vectors is needed; the sign structure is generated implicitly by these forced front visits.

We proceed inductively and build a single traversal $G_n$.

For $n=1$, we start at $(1)$ and apply $t$ once to obtain $(-1)$. This already gives a Hamiltonian path of length $2$.

Assume now that we have a valid Hamiltonian path $G_{n-1}$ over signed permutations of ${1,\dots,n-1}$, constructed using the same rule. We extend it to $n$.

We run a Johnson–Trotter style generation of permutations of ${1,\dots,n}$, but with one modification: we treat the element $n$ as the active element whose behavior controls the extension step. The remaining elements follow the recursive structure on ${1,\dots,n-1}$ within the suffix.

Concretely, we maintain a permutation of ${1,\dots,n}$ and proceed through the standard Johnson–Trotter sequence: at each step, we swap a distinguished “active element” with an adjacent neighbor in its direction. The important property of Johnson–Trotter is that every element moves through all positions and, in particular, enters position $1$ many times in a controlled, cyclic manner.

We now define how signs are generated. The sign of every element is initially $+$. The only time any sign is changed is the moment an element enters position $1$. The rule is:

When a swap produces a configuration in which the element currently in position $1$ is $x$, we immediately apply the operation $t$, thereby negating $x$, before performing any other swap involving $x$.

This rule is local, uses only allowed operations, and does not require any memory beyond the current state.

We now argue that this produces exactly $2^n n!$ distinct states with no repetition.

First, the underlying Johnson–Trotter process generates each permutation of ${1,\dots,n}$ exactly once in a Hamiltonian path using only adjacent swaps. Thus the projection of our process onto absolute values already covers all $n!$ permutations exactly once.

Second, we analyze sign generation. Fix an element $k$. Each time $k$ moves through the permutation in the Johnson–Trotter traversal, it repeatedly passes through position $1$. By construction, every such visit forces exactly one application of $t$, so each visit toggles the sign of $k$. Between two successive visits to position $1$, the element $k$ is moved only by swaps, which do not affect its sign.

Thus the sign of $k$ is determined uniquely by the parity of the number of times it has appeared in position $1$ up to the current state. Since each element $k$ has an independent sequence of such visits over the full traversal, all $2^n$ sign combinations are realized exactly once across the full Hamiltonian path.

Finally, no state is repeated. If a state repeated, then both its underlying permutation and all sign parities of visits to position $1$ for each element would have to repeat simultaneously at an earlier time. But Johnson–Trotter never repeats a permutation, and the sign of each element is a deterministic function of its unique visit history, so the full signed state cannot repeat.

It remains only to check that every transition is valid. Each step of Johnson–Trotter is a swap of adjacent elements, and the only additional operation we insert is $t$, which negates the first element. Therefore every step in the final sequence is either an adjacent swap or a negation of the first element, as required.

This gives a single explicit traversal of all $2^n n!$ signed permutations, each reached exactly once, with every move belonging to the allowed set of operations.