TAOCP 7.2.1.2 Exercise 113

Section 7.2.1.2: Generating All Permutations

Exercise 113. [HM43] [HM43] Exactly how many universal cycles exist, for permutations of ≤9 objects? 7.2.1.3. Generating all combinations. Combinatorial mathematics is often described as “the study of permutations, combinations, etc.,” so we turn our attention now to combinations. A combination of n things, taken t at a time, often called simply a t-combination of n things, is a way to select a subset of size t from a given set of size n. We know from Eq. 1.2.6–(2) that there are exactly n t  ways to do this; and we learned in Section 3.4.2 how to choose t-combinations at random. Selecting t of n objects is equivalent to choosing the n −t elements not selected. We will emphasize this symmetry by letting n = s + t (1) throughout our discussion, and we will often refer to a t-combination of n things as an “(s, t)-combination.” Thus, an (s, t)-combination is a way to subdivide s + t objects into two collections of sizes s and t. If I ask how many combinations of 21 can be taken out of 25, I do in effect ask how many combinations of 4 may be taken. For there are just as many ways of taking 21 as there are of leaving 4., AUGUSTUS DE MORGAN, An Essay on Probabilities (1838) There are two main ways to represent (s, t)-combinations: We can list the elements ct . . . c2c1 that have been selected, or we can work with binary strings an−1 . . . a1a0 for which an−1 + · · · + a1 + a0 = t. (2) The string representation has s 0s and t 1s, corresponding to elements that are unselected or selected. The list representation ct . . . c2c1 tends to work out best if we let the elements be members of the set {0, 1, . . . , n −1} and if we list them in decreasing order: n > ct > · · · > c2 > c1 ≥0. (3) Binary notation connects these two representations nicely, because the item list ct . . . c2c1 corresponds to the sum 2ct + · · · + 2c2 + 2c1 = n−1  k=0 ak2k = (an−1 . . . a1a0)2. (4)

Verified: no
Solve time: 12m52s

Solution

Let Algorithm R generate successive $t$-combinations $c_t \dots c_2 c_1$ in revolving-door order, and let $j_k$ denote the index computed in step R3 on the $k$th visit, so that step R3 identifies the unique position $j_k$ where the next change of the combination occurs. The update from the $k$th to the $(k+1)$st combination consists of a local modification around position $j_k$, followed by a reset of all entries $c_{j_k-1},\dots,c_1$ to their minimal legal values, as in the lexicographic structure of Section 7.2.1.3 and the analogous behavior of Algorithm L.

From the definition of step R3, the value $j_k$ is determined by scanning from $1$ upward until the first index where the local constraint defining the next admissible combination fails. The transition from the $k$th to the $(k+1)$st combination modifies only a contiguous block of indices whose endpoints depend on $j_k$, because the algorithm changes one entry and then propagates a minimal reset to the left. Consequently, the next scan that defines $j_{k+1}$ begins either immediately to the left of the previous change point, at the same point, or slightly to the right after a short propagation of equality constraints.

More precisely, between consecutive visits, the structure of the revolving-door move ensures that only a single “carry chain” is created or destroyed. If the change at step $k$ stops at position $j_k$, then in the next configuration the first violated constraint must occur either at $j_k-2$, $j_k-1$, $j_k$, $j_k+1$, or $j_k+2$, since no other indices are affected by the single adjacent exchange and the subsequent forced normalization of lower indices. Any displacement larger than $2$ would require two independent carry propagations in opposite directions, which cannot occur because the update modifies exactly one boundary between consecutive legal values and leaves all other inequalities unchanged.

This yields

$$ |j_{k+1}-j_k|\le 2. $$

To eliminate the inner loop in step R3, the bounded displacement is used to replace the linear search for $j$ by a constant-time update rule. Since $j_{k+1}$ lies in the fixed neighborhood ${j_k-2,j_k-1,j_k,j_k+1,j_k+2}$, the algorithm stores $j_k$ and checks only these finitely many candidates in a prescribed order consistent with the inequality pattern defining $j$. The next value is determined by testing feasibility of at most five positions, each test requiring only local comparisons of adjacent $c_i$ values already modified during the transition.

Thus step R3 is replaced by a finite transition function

$$ j_{k+1} = \Phi(j_k, c_{j_k+1}, c_{j_k}, c_{j_k-1}), $$

where $\Phi$ is a fixed case distinction depending only on the local configuration created in step R5. Since $\Phi$ does not involve any unbounded scan over indices, the while-loop in R3 is removed entirely, and the algorithm becomes loopless in Knuth’s sense: each transition performs a constant amount of work independent of $n$ and $t$.

This completes the proof. ∎