TAOCP 7.2.1.3 Exercise 38
An $(s,t)$-combination is represented in this section as a strictly decreasing sequence $c_t > c_{t-1} > \cdots > c_1 \ge 0,$ with $c_j \in {0,1,\dots,n-1}$ and $n=s+t$, satisfying condition (3).
Section 7.2.1.3: Generating All Combinations
Exercise 38. [26] [26] Design a genlex algorithm like Algorithm C for the reverse sequence CR st.
Verified: no
Solve time: 13m25s
Setup
An $(s,t)$-combination is represented in this section as a strictly decreasing sequence
$c_t > c_{t-1} > \cdots > c_1 \ge 0,$
with $c_j \in {0,1,\dots,n-1}$ and $n=s+t$, satisfying condition (3). Algorithm L generates these sequences in lexicographic order by repeatedly increasing the rightmost admissible entry and resetting the suffix to its lexicographically least completion.
Let $C_{st}^R$ denote the reverse lexicographic order on $(s,t)$-combinations, that is, the order obtained by reversing the lexicographic order of the tuples $(c_t,\dots,c_1)$.
The task is to construct a genlex algorithm in the style of Algorithm C that generates all $(s,t)$-combinations in the sequence $C_{st}^R$.
Solution
The reverse lexicographic order starts from the lexicographically largest combination. This is obtained by maximizing each coordinate subject to the strict decrease condition (3), hence the initial element is
$c_j \leftarrow n-t+j-1 \quad (1 \le j \le t).$
Each step of a genlex method modifies the rightmost position that can change while preserving feasibility, then forces the suffix into the unique extremal completion consistent with the ordering direction.
For reverse lexicographic order, the sequence is decreasing, so the next element is obtained by decreasing the rightmost coordinate that can still be decreased while respecting the lower bounds $c_j \ge j-1$.
Let $j$ be the largest index such that $c_j > j-1$. If no such $j$ exists, then the current combination is $(t-1,t-2,\dots,0)$ and the algorithm terminates.
Once such a position $j$ is found, the value $c_j$ is decreased by one:
$c_j \leftarrow c_j - 1.$
After this change, the suffix $c_{j-1},c_{j-2},\dots,c_1$ must be reset to the lexicographically largest configuration consistent with the new $c_j$. The maximal decreasing completion under constraint (3) is obtained by forcing consecutive descent:
$c_k \leftarrow c_{k+1} - 1 \quad (k=j-1,j-2,\dots,1).$
This produces the unique maximal suffix because each inequality $c_{k+1} > c_k$ is tight and each $c_k$ is as large as possible subject to $c_k \ge k-1$ and $c_k < c_{k+1}$.
Algorithm $C_{st}^R$ (reverse genlex combinations)
Assume $n \ge t \ge 0$ and $n=s+t$.
Introduce a sentinel $c_0 \leftarrow -1$ for convenience.
R1. [Initialize.] Set $c_j \leftarrow n-t+j-1$ for $1 \le j \le t$.
R2. [Visit.] Visit $c_t c_{t-1} \dots c_1$.
R3. [Find $j$.] Set $j \leftarrow t$. While $c_j = j-1$, set $j \leftarrow j-1$. If $j=0$, terminate the algorithm.
R4. [Decrease.] Set $c_j \leftarrow c_j - 1$.
R5. [Rebuild suffix.] For $k \leftarrow j-1, j-2, \dots, 1$, set $c_k \leftarrow c_{k+1} - 1$. Return to R2.
Verification
The initial state is the unique maximal $(s,t)$-combination because $c_t=n-1$ and each successive entry is forced by strict decrease, hence $c_j=n-t+j-1$.
Every step modifies exactly one index $j$ satisfying $c_j>j-1$, so feasibility is preserved since after decrement $c_j-1 \ge j-1$ still holds.
The suffix reconstruction ensures strict inequalities $c_{k+1}>c_k$ for all $k<j$, because $c_k=c_{k+1}-1$ holds by construction, and thus $c_k \ge k-1$ follows inductively from $c_j-1 \ge j-1$.
If no index satisfies $c_j>j-1$, then $c_j=j-1$ for all $j$, giving the minimal lexicographic element, so termination is correct.
Each execution produces the immediate predecessor in lexicographic order because the largest possible decrease is made at the rightmost feasible position, and the suffix is maximized subject to that decrease, which matches the definition of reverse lexicographic adjacency for decreasing sequences.
Every $(s,t)$-combination is reachable since repeated application eventually reduces each coordinate to its lower bound, and no state repeats because each step strictly decreases the lexicographic value.
This completes the construction of a genlex algorithm generating $C_{st}^R$. ∎