Skip to main content

Walkthrough — Module 08: Combinatorial Generation

Read this AFTER a stage is green — it explains how the reference solution is built and why.

Stage 1: Gray binary code​

gray_code follows Algorithm 7.2.1.1G literally: a loop that visits (out.push(a)), flips the parity bit (a_inf = 1 - a_inf), chooses j (G4), and complements bit j (G5), terminating when j == n. The invariant is that after visiting the k-th word, a_inf holds the parity of k+1, and G4's rule — flip bit 0 when parity is odd, else flip a.trailing_zeros() + 1 — reproduces the ruler-function flip position ρ(k) without ever computing k or maintaining a counter. Keeping the entire n-tuple packed in one u64 is the idiom worth stealing: "position of the rightmost 1-bit" becomes the single intrinsic trailing_zeros(), and complementing a bit is a ^= 1 << j. The subtle correctness point is the + 1 offset — Knuth's j is one more than the rightmost-1 position, and j == n (not n-1) is the termination signal, so an off-by-one there would either stop early or index past the top bit. gray_rank inverts g(k) = k ^ (k>>1) by the prefix-XOR fold while g != 0 { k ^= g; g >>= 1; }, which is the closed-form solution of the triangular bit equations, far cheaper than a table lookup.

Stage 2: Permutations in lexicographic order​

next_permutation mutates the slice in place and returns a bool, exactly mirroring Knuth's "terminate if j = 0": on the last (non-increasing) permutation it returns false and leaves a untouched, so all_permutations can drive it with a clean while next_permutation(&mut a) { ... }. The three steps map one-to-one: L2 walks 1-based j down while a[j-1] >= a[j] to locate the pivot before the longest non-increasing suffix, L3 finds the rightmost l with a[j-1] < a[l-1] and swaps, and L4 does a[j..].reverse(). The decisive design choice is >= rather than > in both scans: because the suffix is non-strictly decreasing, reversing it in L4 sorts it in O(length) instead of O(length log length), and — the real payoff — equal elements are treated as an already-maximal run, so a multiset like [1,2,2,3] yields each of its 12 distinct arrangements exactly once instead of over-counting by swapping equal values. This is precisely the algorithm C++'s std::next_permutation ships; a naive "generate all n! then dedup" version would be both slower and wrong on multisets.

Stage 3: Plain changes: adjacent transpositions​

plain_changes implements Algorithm 7.2.1.2P with two parallel control vectors c and o sized n+1 (index 0 unused, so the code reads 1-based just like the book) plus the offset s. The outer loop visits; the inner loop is steps P4–P7: it walks j down from n, computing q = c[j] + o[j], and the first j with q in range [0, j) is the largest element with room to move — it performs the adjacent swap a.swap(u-1, v-1) (the -1 converting Knuth's 1-based a_{j-c_j+s} / a_{j-q+s} to Rust indices) and breaks back to visiting. The invariant tying it together: c_j is an odometer bounded by j and o_j its sweep direction, so an element that reaches either end (q == j or q < 0) reverses direction in P7 and hands control to a smaller element, which is the boustrophedon weave made iterative. Using signed i64 for c, o, s, and the intermediate u/v is the idiom that matters — the arithmetic j - c[j] + s and the q < 0 test both go negative mid-computation, so doing it in usize would underflow and panic. The n = 0 case returns vec![vec![]], the single empty permutation, rather than an empty list.

Stage 4: Generating combinations​

combinations stores the k-subset in c[1..=t] with sentinels c[t+1] = n and c[t+2] = 0, giving a buffer of length t+3 so the T4 lookahead c[j+1] is always in bounds. Structuring the body as one loop with the post-visit branch — if j > 0 { x = j; } jumps directly to T6, otherwise the easy case c[1]+1 < c[2] bumps the smallest element and continues — makes the common path genuinely O(1): most successors just increment c_1, and only when it collides with c_2 does the T4 inner loop reset the low run (c[j-1] = j-2) and scan upward for the first element with room. The sentinels are the idiom worth stealing: c[t+1] = n stops the upward scan without a separate bounds test and c[t+2] = 0 guards the reset, so the hot loop carries no boundary ifs. The reference explicitly special-cases t == 0 (one empty combination) and t == n (one full combination) before running T, because Algorithm T is only valid for 0 < k < n; the assert!(k <= n, ...) guards the nonsensical k > n. Output is emitted ascending (c_1 < ... < c_k) even though the visiting order is colexicographic — the "prefix stability" property (the (n,k) list is a prefix of the (n',k) list) is what makes colex the natural order for ranking with the combinatorial number system.

Stage 5: Partitions of an integer​

partitions runs Algorithm 7.2.1.4P with a[0] as a zero sentinel and q always indexing the rightmost part greater than 1. The nested-loop shape reflects Knuth's two regimes: the inner loop visits and, while a[q] == 2, cheaply splits a trailing 2 into 1+1 (P4) — the overwhelmingly common case — and only P5/P6 does the general work of decreasing a_q to x = a_q - 1 and redistributing the remainder rem into copies of x. Reusing a mutable rem for Knuth's repurposed n (the amount still to place) is the faithful touch; termination is q == 0. partition_count is a deliberately separate function, not derived from enumeration: it builds p[0..=n] bottom-up via the pentagonal-number recurrence, iterating k only while g1 = k(3k-1)/2 <= m (about √m terms) with alternating signs — computed in i128 to hold intermediate magnitudes and returned as u64, so p(100) = 190569292 falls out instantly where listing all of them never could. conjugate computes part j as p.iter().take_while(|&&x| x >= j).count() — reading the Ferrers diagram by columns — and asserts non-increasing (message contains "non-increasing") and positive parts up front; because it is a clean involution, the test can round-trip conjugate(conjugate(p)) == p over every partition of 8 and confirm the "number of parts ↔ largest part" statistic swap.