TAOCP 7.2.1.2 Exercise 61

Section 7.2.1.2: Generating All Permutations

Exercise 61. [21] [21] Continuing the previous exercise, a Gray code for permutations is like a Gray cycle except that the final permutation πn!−1 is not required to be adjacent to the initial permutation π0. Study the set of all Gray codes for n = 4 that start with 1234.

Verified: no
Solve time: 4m39s

Solution

Let $\beta_0,\ldots,\beta_{M-1}$ be a revolving-door listing of all $(s,t)$-combinations of ${0,1,\ldots,s+t-1}$, where $M=\binom{s+t}{t}$, and consecutive terms differ by a single adjacent exchange in the corresponding binary string representation. Let $\alpha_0,\ldots,\alpha_{N-1}$ list all permutations of the multiset ${s_0\cdot 0,s_1\cdot 1,\ldots,s_d\cdot d}$, where adjacent permutations differ by a single interchange of two elements.

For each fixed $j$, define $\Lambda_j$ as the sequence obtained by starting from $\alpha_j \uparrow \beta_0$ and then applying the same sequence of exchanges that transforms $\beta_k$ into $\beta_{k+1}$. The operation $\alpha \uparrow \beta$ substitutes the elements of $\alpha$ into the positions of the $1$-bits of $\beta$ in left-to-right order, leaving the $0$-positions filled by the remaining symbols of $\alpha$ in their relative order.

Let $w(\beta)$ denote the binary word of $\beta$, and let $P(\alpha \uparrow \beta)$ denote the resulting multiset permutation. The mapping $\beta \mapsto \alpha \uparrow \beta$ is a bijection between $(s,t)$-combinations and permutations of the multiset ${s_0\cdot 0,\ldots,s_d\cdot d}$ with fixed multiplicities, because each $1$-position selects exactly one element of $\alpha$ and preserves order within selected and unselected blocks.

The revolving-door property of $\beta$ states that $\beta_{k+1}$ is obtained from $\beta_k$ by exchanging a $1$ and an adjacent $0$ in the binary string. This exchange modifies exactly one selected position in the induced multiset permutation: in $\alpha_j \uparrow \beta_k$, the element occupying the moved $1$-position is swapped with the element occupying the adjacent $0$-position.

Since the substitution $\alpha_j \uparrow \beta_k$ preserves the left-to-right ordering of symbols within selected and unselected subsequences, an adjacent $10 \leftrightarrow 01$ exchange in $\beta_k$ corresponds to an interchange of the two elements occupying the corresponding adjacent positions in $\alpha_j \uparrow \beta_k$. Hence consecutive terms in $\Lambda_j$ differ by a single interchange of two elements.

It remains to show that the concatenation over all $j$ covers all permutations of ${s_0\cdot 0,s_1\cdot 1,\ldots,s_d\cdot d}$. Each permutation $\pi$ of this multiset determines uniquely its pattern of positions of equal symbols, which yields a binary word $\beta(\pi)$ indicating the locations of the $t=s_1+\cdots+s_d$ nonzero symbols relative to the $s_0$ zeros. This binary word is an $(s_0,t)$-combination, hence it equals some $\beta_k$. The restriction of $\pi$ to the nonzero symbols defines a permutation $\alpha_j$ of ${1,\ldots,d}$ consistent with multiplicities $s_1,\ldots,s_d$, and the relative order of equal symbols fixes $j$ uniquely because $\alpha_0,\ldots,\alpha_{N-1}$ lists all such multiset permutations.

Thus every $\pi$ is uniquely represented as $\alpha_j \uparrow \beta_k$ for some pair $(j,k)$. Since $\beta_k$ ranges over all combinations and $\alpha_j$ ranges over all multiset permutations, the union of all $\Lambda_j$ contains every permutation exactly once.

This establishes that the list formed by all $\Lambda_j$ contains all permutations of ${s_0\cdot 0,\ldots,s_d\cdot d}$. ∎