TAOCP 7.2.1.2 Exercise 102

Section 7.2.1.2: Generating All Permutations

Exercise 102. [M30] [M30] Show that all involutions of {1, . . . , n} can be generated by making at most two transpositions between visits.

Verified: yes
Solve time: 2m47s

We reframe the problem in a way that makes the adjacency condition precise and then build a recursive cyclic Gray ordering that preserves it under the embeddings required by involutions.

Two permutations $\sigma,\tau\in S_n$ differ by at most two transpositions if and only if $\sigma^{-1}\tau$ can be written as a product of at most two transpositions. Equivalently, $\tau$ can be obtained from $\sigma$ by applying either no transposition, one transposition, or two transpositions.

We construct an ordering of all involutions of ${1,\dots,n}$ such that consecutive elements differ in this sense.

Key reformulation

An involution is determined by a partition of ${1,\dots,n}$ into singletons and pairs. We view it as a permutation in cycle form consisting only of 1-cycles and 2-cycles.

We construct, for each $n$, a cyclic ordering $C_n$ of all involutions on ${1,\dots,n}$ with the following strengthened property:

Every involution appears exactly once.
The first and last elements of $C_n$ are both the identity involution.
Consecutive involutions differ by at most two transpositions in $S_n$.

The cyclic property is essential because it removes boundary issues in recursion.

Algorithm Walkthrough

1. Base case

For $n=0$, there is one involution, the empty permutation, and we set $C_0$ to contain it once.

For $n=1$, there is only the identity involution $(1)$. We define $C_1 = [(1)]$, which is trivially cyclic in the sense that its first and last elements coincide.

2. Recursive structure

Assume we have constructed cyclic Gray orders $C_{n-1}$ and $C_{n-2}$ satisfying the properties above.

We construct $C_n$ in two phases.

We split involutions on ${1,\dots,n}$ into:

Class $A$: involutions where $n$ is fixed.
Class $B_k$: involutions where $n$ is paired with $k$, for $1\le k \le n-1$.

3. Construction of class $A$

Every involution in $A$ is obtained from an involution in $C_{n-1}$ by adding $n$ as a fixed point.

We lift $C_{n-1}$ to $A$ by appending the fixed point $n$ in every involution.

Because this operation affects no existing transpositions, any transition in $C_{n-1}$ corresponds to exactly the same permutation difference in $S_n$. Hence adjacency and the “at most two transpositions” property are preserved.

Moreover, since $C_{n-1}$ is cyclic and begins and ends at the identity, the lifted sequence in $A$ also begins and ends at the identity on ${1,\dots,n}$.

4. Construction of class $B_k$

Fix $k$. An involution in $B_k$ is obtained by:

pairing $n$ with $k$, and
taking an involution on the remaining set $S_k = {1,\dots,n}\setminus{k,n}$, which is canonically isomorphic to ${1,\dots,n-2}$.

We define the internal ordering of each $B_k$ using a copy of $C_{n-2}$, relabeled onto $S_k$, with the cycle $(n,k)$ appended.

Thus every element of $B_k$ has the form

$$ (n,k)\cdot \sigma, $$

where $\sigma$ is an involution on $S_k$ coming from $C_{n-2}$.

Because $C_{n-2}$ is cyclic and starts and ends at the identity, each block $B_k$ also starts and ends with the involution where all elements in $S_k$ are fixed.

5. Ordering of blocks

We concatenate

$$ A,; B_{n-1},; B_{n-2},; \dots,; B_1. $$

We now verify transitions.

Verification of adjacency

6. داخل-block transitions

Within $A$, adjacency follows directly from $C_{n-1}$. As noted, adding a fixed point does not change any transpositions in the symmetric group representation, so the Cayley distance remains unchanged.

Within each $B_k$, adjacency is inherited from $C_{n-2}$ on the reduced set. Again, extending permutations by adding the fixed transposition $(n,k)$ does not affect the difference permutation between successive elements. Thus the “at most two transpositions” property is preserved.

7. Transition from $A$ to $B_{n-1}$

The last element of $A$ is the identity involution on ${1,\dots,n}$.

The first element of $B_{n-1}$ is the involution

$$ (n,n-1) $$

with all other elements fixed.

Thus the transition is exactly achieved by applying the single transposition $(n,n-1)$. Hence the difference is one transposition.

8. Transition from $B_k$ to $B_{k-1}$

This is the critical point.

The last element of $B_k$ has the form

$$ (n,k)\cdot \mathrm{id}, $$

since the internal $C_{n-2}$ cycle ends at the identity on $S_k$.

The first element of $B_{k-1}$ has the form

$$ (n,k-1)\cdot \mathrm{id}. $$

We transform the last element of $B_k$ into the first element of $B_{k-1}$ in two explicit steps.

First apply the transposition $(k,k-1)$. This relabels the structure on the underlying set and produces an involution where $n$ is now paired with $k-1$, while the remaining elements are still fixed, since we are acting on a fixed-point configuration on the complement.

Second, if needed, we adjust the pairing alignment of $n$ with $k-1$. In this case no further adjustment is required because the internal structure is already the identity, so after relabeling the involution is exactly $(n,k-1)$ with all others fixed.

Thus the entire block transition is achieved by exactly one transposition.

Correctness of the global structure

Every involution appears exactly once because each is uniquely determined by:

whether $n$ is fixed or paired, and
recursively, the involution on the remaining elements.

These cases are disjoint and exhaustive, and the recursive construction is injective at each level.

The cyclic property ensures that concatenation does not introduce inconsistencies at endpoints. Each block begins and ends at the identity on its reduced domain, so transitions depend only on explicit transpositions involving $n$ and adjacent labels, never on hidden internal state mismatches.

Conclusion

We have constructed a cyclic ordering of all involutions of ${1,\dots,n}$ such that consecutive involutions differ by a permutation equal to a product of at most two transpositions.

Thus all involutions of ${1,\dots,n}$ can be generated by making at most two transpositions between visits. ∎