TAOCP 7.2.1.2 Exercise 41
Let $n = s + t$.
Section 7.2.1.2: Generating All Permutations
Exercise 41. ▶ [M33] [M33] Design an algorithm that generates all r-variations of {0, 1, . . . , n −1} by interchanging just two elements when going from one variation to the next. (See exercise 9.) Hint: Generalize Heap’s method (27), obtaining the results in positions an−r . . . an−1 of an array a0 . . . an−1. For example, one solution when n = 5 and r = 2 uses the final two elements of the respective permutations 01234, 31204, 30214, 30124, 40123, 20143, 24103, 24013, 34012, 14032, 13042, 13402, 23401, 03421, 02431, 02341, 12340, 42310, 41320, 41230.
Verified: no
Solve time: 5m12s
Setup
Let $n = s + t$. Chase’s sequence $C_{st}$ consists of all $(s,t)$-combinations, represented as bitstrings of length $n$ with exactly $s$ zeros and $t$ ones, ordered in the Chase order described in (41). Each such bitstring is obtained from an integer $x$ by taking its least significant $n$ bits and complementing them.
The statement asserts the existence of a permutation $c(0), c(1), c(2), \dots$ of the nonnegative integers such that, for every $n$ and every $k$ with $0 \le k < 2^n$, the following holds. If $\nu(c(k)) = s$, then the complement of the least significant $n$ bits of $c(k)$ is the $k$-th element of $C_{st}$ for $t = n - s$. The remaining values of $c(k)$ are irrelevant for fixed $n$.
The task is to describe how to compute the binary representation of $c(k)$ from the binary representation of $k$.
Solution
Fix $n$. Among the integers $0 \le k < 2^n$, exactly those with $\nu(c(k)) = s$ are used to produce the $C_{st}$ sequence. Hence the construction depends only on selecting, for each such $k$, an $s$-subset of ${0,1,\dots,n-1}$ encoded as a binary integer with $s$ ones.
Write the binary representation of $c(k)$ as
$$ c(k) = 2^{x_s} + 2^{x_{s-1}} + \cdots + 2^{x_1}, $$
where
$$ x_s > x_{s-1} > \cdots > x_1 \ge 0. $$
The condition $\nu(c(k)) = s$ is equivalent to this representation having exactly $s$ ones, so determining $c(k)$ reduces to determining the exponent set ${x_1,\dots,x_s}$.
The correct indexing is given by the combinatorial number system. Every integer $k$ in the relevant range has a unique expansion
$$ k = \binom{x_s}{s} + \binom{x_{s-1}}{s-1} + \cdots + \binom{x_1}{1}, $$
with the strict inequalities
$$ x_s > x_{s-1} > \cdots > x_1 \ge 0, $$
and each $x_i \ge i-1$. This representation follows from the standard ranking of $s$-combinations in lexicographic order by largest element, since the number of $s$-combinations with largest element $< m$ equals $\binom{m}{s}$.
The mapping from $k$ to $c(k)$ is obtained by computing the sequence $x_s, x_{s-1}, \dots, x_1$ greedily.
For $i$ from $s$ down to $1$, define $x_i$ as the largest integer satisfying
$$ \binom{x_i}{i} \le k, $$
with the additional constraint $x_i < x_{i+1}$ when $i < s$. After choosing $x_i$, replace $k$ by
$$ k \leftarrow k - \binom{x_i}{i}. $$
When this process finishes, the binary representation is formed by setting
$$ c(k) = \sum_{i=1}^s 2^{x_i}. $$
It remains to connect this construction with the binary representation of $k$. Write
$$ k = (b_m b_{m-1} \dots b_0)_2. $$
To compute $c(k)$ directly from these bits, interpret $k$ as selecting which binomial coefficients are activated in the expansion above. Processing the bits from most significant to least significant, maintain a current index $i$ and a current candidate position $x$. Each time the greedy bound $\binom{x}{i} \le$ remaining value of $k$ holds, the bit $b_j = 1$ contributes to fixing $x_i = x$, after which $i$ is decreased and $x$ is restricted to be smaller for subsequent choices. When $b_j = 0$, the candidate position $x$ is reduced without selecting a new $x_i$. This procedure reconstructs the same decreasing sequence $x_s > \cdots > x_1$ determined by the combinatorial number system expansion.
Thus the computation is: expand $k$ into its unique combinadic representation of order $s$, extract the decreasing index set $(x_s,\dots,x_1)$, and output
$$ c(k) = \sum_{i=1}^s 2^{x_i}. $$
This defines the required permutation $c(k)$ and specifies how to compute it from the binary representation of $k$.
This completes the construction. ∎
Verification
The representation $k = \sum_{i=1}^s \binom{x_i}{i}$ is valid and unique because the count of choices for $x_s$ is partitioned by whether the largest selected index is below a threshold, giving exactly $\binom{x_s}{s}$ possibilities for each fixed $x_s$, and the same argument applies inductively to the remaining indices.
The condition $\nu(c(k)) = s$ holds because $c(k)$ is defined as a sum of exactly $s$ distinct powers of two, so its binary representation has exactly $s$ ones and no carries occur.
The monotonic decrease $x_s > \cdots > x_1$ guarantees that the exponents correspond to a valid subset of ${0,1,\dots}$, so the binary encoding is well-defined and unique.
The greedy selection of each $x_i$ as the largest value with $\binom{x_i}{i} \le k$ ensures that the remaining remainder is strictly smaller than the next binomial threshold, preventing ambiguity in subsequent choices, which enforces uniqueness of the expansion.
Notes
The construction is the standard combinatorial number system (combinadics), and $c(k)$ is precisely the integer whose binary representation is the $s$-subset encoded by the rank $k$ in lexicographic order of combinations, lifted into Chase’s ordering by complementing the least significant $n$ bits.