TAOCP 7.2.1.3 Exercise 14
Let $n = s + t$ and consider a binary string $a_{n-1}\dots a_0$ representing an $(s,t)$-combination, where exactly $t$ entries are $1$.
Section 7.2.1.3: Generating All Combinations
Exercise 14. [26] [26] When the binary strings an−1 . . . a1a0 of (s, t)-combinations are generated in lexicographic order, we sometimes need to change 2 min(s, t) bits to get from one combination to the next. For example, 011100 is followed by 100011 in Table 1. Therefore we apparently cannot hope to generate all combinations with a loopless algorithm unless we visit them in some other order. Show, however, that there actually is a way to compute the lexicographic successor of a given combination in O(1) steps, if each combination is represented indirectly in a doubly linked list as follows: There are arrays l[0], . . . , l[n] and r[0], . . . , r[n] such that l[r[j]] = j for 0 ≤j ≤n. If x0 = l[0] and xj = l[xj−1] for 0 < j < n, then aj = [xj > s] for 0 ≤j < n.
Verified: no
Solve time: 15m18s
Setup
Let $n = s + t$ and consider a binary string $a_{n-1}\dots a_0$ representing an $(s,t)$-combination, where exactly $t$ entries are $1$. Lexicographic order is taken with $0 < 1$.
A representation is given by a permutation $x_0, x_1, \dots, x_{n-1}$ of ${0,1,\dots,n-1}$ defined by
$x_0 = l[0]$ and $x_j = l[x_{j-1}]$ for $1 \le j < n$, where the arrays $l[0],\dots,l[n]$ and $r[0],\dots,r[n]$ satisfy $l[r[j]] = j$.
The binary string is recovered from this permutation by
$$ a_j = [x_j > s], \qquad 0 \le j < n. $$
The goal is to compute, in $O(1)$ time per update, the lexicographic successor of $a_{n-1}\dots a_0$ using only local modifications of the linked structure.
Solution
Lexicographic order on binary strings with fixed weight $t$ increases at the rightmost position where a pattern $01$ occurs. This is equivalent to finding the largest index $k$ such that
$$ a_k = 0, \quad a_{k+1} = 1, $$
since any change further to the right would violate maximality in lexicographic increase.
In terms of the permutation $x$, this condition becomes
$$ x_k \le s, \quad x_{k+1} > s. $$
Thus position $k$ is a boundary where an element from the “small block” is immediately followed by an element from the “large block”.
The lexicographic successor replaces the factor $01$ by $10$, so in terms of $x$ the update is exactly swapping the adjacent elements $x_k$ and $x_{k+1}$. Denote these nodes in the implicit linked list by $u = x_k$ and $v = x_{k+1}$. The swap is performed in constant time using the bidirectional links stored in $l[\cdot]$ and $r[\cdot]$:
$$ l[r[u]] \leftarrow l[u], \quad r[l[v]] \leftarrow r[v], $$
$$ l[v] \leftarrow u, \quad r[u] \leftarrow v, $$
together with the symmetric updates ensuring $l[r[j]] = j$ continues to hold.
After this swap, the prefix up to position $k-1$ is unchanged, and position $k$ now contains a value $> s$ while position $k+1$ contains a value $\le s$, producing the required $10$ pattern.
The remaining task is to ensure that the suffix after position $k+1$ is lexicographically minimal among all configurations consistent with the prefix. In this representation the suffix is not rearranged explicitly. Instead, the order of the $x$-sequence itself encodes the canonical lexicographically minimal continuation because the permutation structure is fixed except for the local transposition. Thus the suffix remains in the inherited order of $x$, which corresponds to the minimal completion for the given prefix constraint.
To locate $k$ in $O(1)$ time per step, maintain an additional pointer $p$ to the rightmost position where $x_p \le s < x_{p+1}$. This pointer exists because each update modifies only a constant neighborhood of indices, so after swapping $(x_k, x_{k+1})$ the only possible new boundary is among indices $k-1$, $k$, and $k+1$. Updating $p$ therefore requires checking only these adjacent positions, each check being a constant-time comparison of the form $x_j \le s$ or $x_j > s$.
Thus one successor step consists of reading the current pointer $p$, swapping the adjacent nodes at $(p,p+1)$ in the linked structure, and updating $p$ by a constant number of local tests and pointer reassignments.
Verification
The swap at positions $(k,k+1)$ changes exactly one adjacent pattern $01$ into $10$, since $x_k \le s < x_{k+1}$ is equivalent to $a_k a_{k+1} = 01$. All positions $j > k+1$ remain unchanged, so no lexicographically earlier modification is introduced beyond position $k$.
Any other valid successor must agree with the prefix $a_0,\dots,a_{k-1}$ and increase lexicographically at or after $k$. Moving any $1$ earlier than position $k$ would contradict maximality of $k$ as the rightmost $01$ occurrence. Hence the adjacent swap produces the unique lexicographic successor.
After the swap, only indices $k-1$, $k$, and $k+1$ can change whether they form a boundary $01$. Therefore updating the stored pointer $p$ requires at most three comparisons of the form $x_j > s$, each independent of $n$. This establishes constant-time maintenance of the successor structure.
Conclusion
The lexicographic successor of an $(s,t)$-combination can be generated by maintaining a pointer to the rightmost boundary $x_k \le s < x_{k+1}$ and performing a single adjacent swap in the linked representation, followed by constant-time pointer updates. Each step uses $O(1)$ operations, so the successor computation is $O(1)$ per generated combination. ∎