TAOCP 7.2.1.2 Exercise 47
Let $C_t(n)$ denote the lexicographically ordered sequence of all $t$-combinations $c_t \ldots c_1$ of ${0,1,\ldots,n-1}$ in the sense of Algorithm L.
Section 7.2.1.2: Generating All Permutations
Exercise 47. ▶ [M21] [M21] Express the number of times that each step of Algorithm X is performed in terms of the numbers N0, N1, . . . , Nn, where Nk is the number of prefixes a1 . . . ak that satisfy tj(a1, . . . , aj) for 1 ≤j ≤k.
Verified: no
Solve time: 4m21s
Solution
Let $C_t(n)$ denote the lexicographically ordered sequence of all $t$-combinations $c_t \ldots c_1$ of ${0,1,\ldots,n-1}$ in the sense of Algorithm L. Let $C_t(n)^{-1}$ be obtained by deleting every combination with $c_1 = 0$ and then replacing each remaining $c_t \ldots c_1$ by $(c_t-1)\ldots(c_1-1)$.
Let $\mathcal{S}$ be the set of all $t$-combinations of ${0,1,\ldots,n-1}$ with $c_1 \ge 1$. Every element of $\mathcal{S}$ can be written uniquely as $c_t \ldots c_1$ with $n-1 \ge c_t > \cdots > c_1 \ge 1$.
Define a mapping
$\phi(c_t,\ldots,c_1) = (c_t-1,\ldots,c_1-1).$
This is well defined because $c_1 \ge 1$ implies $c_i - 1 \ge 0$ for all $i$, and the strict inequalities are preserved:
$c_t > \cdots > c_1 \quad \Longrightarrow \quad c_t-1 > \cdots > c_1-1.$
Thus $\phi$ is a bijection from $\mathcal{S}$ onto the set of all $t$-combinations of ${0,1,\ldots,n-2}$.
Let $D_t(n)$ denote the sequence $C_t(n)^{-1}$. The preceding bijection shows that $D_t(n)$ is exactly the lexicographic sequence $C_t(n-1)$, because lexicographic comparison of sequences $c_t \ldots c_1$ depends only on the relative order of coordinates, and subtracting $1$ from every coordinate preserves all comparisons:
$(c_t,\ldots,c_1) <{\mathrm{lex}} (d_t,\ldots,d_1) ;\Longleftrightarrow; (c_t-1,\ldots,c_1-1) <{\mathrm{lex}} (d_t-1,\ldots,d_1-1).$
Hence $C_t(n)^{-1} = C_t(n-1)$.
The sequence $C_t(n)$ generated by Algorithm L is lexicographic, and consecutive elements differ by the standard single-increment-and-repair rule described in step L3 and L5. This construction yields a path in the Johnson graph on $t$-subsets of ${0,\ldots,n-1}$ in which each transition replaces a suffix $c_j \ldots c_1$ by its lexicographically minimal completion after increasing $c_j$ by $1$. Each such transition changes exactly one coordinate by $+1$ and leaves all larger coordinates unchanged, so each consecutive pair is adjacent in the Johnson graph.
Since $C_t(n-1)$ is obtained from $C_t(n)$ by a uniform relabeling of vertices via $\phi$, adjacency is preserved under $\phi$ and every consecutive pair in $C_t(n)^{-1}$ remains adjacent in the corresponding Johnson graph on ${0,\ldots,n-2}$. Therefore $C_t(n)^{-1}$ is a Hamiltonian path in that graph.
The only possible failure of perfection arises from endpoints. In $C_t(n)$, the first combination is $t-1, t-2, \ldots, 0$, and the last is $n-1, n-2, \ldots, n-t$. After removing those with $c_1=0$, the first surviving element has $c_1=1$, and after subtraction it becomes $t-2, t-3, \ldots, 0$, while the last element becomes $n-2, n-3, \ldots, n-t-1$. These endpoints are consistent with the structure of $C_t(n-1)$ but do not necessarily close into a cycle under the same successor rule.
Thus $C_t(n)^{-1}$ is a Hamiltonian path obtained from the lexicographic construction on $n-1$ symbols, preserving adjacency but not necessarily the wrap-around connection that would make it perfect in cyclic form. In the terminology of Section 7.2.1.3, this is precisely a near-perfect sequence.
This completes the proof. ∎