This chapter surveys three foundational combinatorial operations on sequences—Cartesian products, permutations, and combinations—and shows how clear, fluent implementations illuminate deep mathematical structure. The narrative emphasizes working with general sequences (not only sets), contrasts eager with lazy generation, and repeatedly leverages the question “what is the p‑th result?” to uncover number‑decomposition schemes. Ordering choices (lexicographic, change‑ringing, shuffle order) and practical performance concerns (amortized vs worst‑case behavior, O(n) vs O(n log n)) are treated as first‑class design forces throughout.
For Cartesian products, the text moves from simple nested loops to extension methods that operate on sets or arbitrary sequences, including a projection form that fuses product and map. It then generalizes to an arbitrary number of input sequences via a sequence‑of‑sequences API that yields sequences of equal‑typed elements, handling edge cases cleanly and building results lazily with query composition. Using an immutable deque to append without mutation, the construction is O(n) to build the composed query and O(n) per produced tuple; it preserves input order and, when inputs are sorted, emits results in lexicographic order. This leads to a concrete link with positional notation: taking the product of a digit set with itself enumerates all fixed‑length numbers, making the bridge from combinatorics to integer representations explicit.
Permutation generation is explored through several complementary methods: Narayana Pandita’s in‑place “next lexicographic” algorithm (supports duplicates, amortized O(1) per permutation), direct access to the p‑th lexicographic permutation via the factorial‑base (Lehmer code) with big‑integer arithmetic, and the Fisher–Yates shuffle, whose random steps can themselves be read as factorial‑base digits to define a non‑lexicographic permutation order with O(n) swaps. The chapter also presents “change ringing” orderings: a recursive adjacent‑swap construction and Even’s array‑based algorithm using “mobile” elements and direction flags to produce each new permutation by one adjacent swap in O(n) time. Combinations receive analogous treatment: a right‑to‑left lexicographic “next” mutator and a pure recursive generator using an immutable deque; counting via an efficient iterative n choose k; and bidirectional indexing—generating the p‑th combination and computing a combination’s index—culminating in the combinatorial number system (Macaulay/Lehmer representation), where any index p uniquely decomposes as a sum of binomial coefficients, mirroring the factorial‑base story for permutations.
Summary
The basic combinatoric operations on finite sequences – the Cartesian product, enumeration of permutations, and enumeration of combinations – are not typically supplied by standard libraries, but they are useful for generating test cases and many other practical applications.
A Cartesian product is essentially a hidden nested loop. We can compute the Cartesian product of 2, 3, 4, … sequences or sets by writing a little helper method with that many nested loops. Sticking a projection function on the end instead of returning a tuple is also quite useful.
To compute the Cartesian product of n sequences where n is only known at runtime, we can make a lazy method that aggregates a nested query object to do this work.
If you want to enumerate permutations of a collection containing duplicates and don’t mind mutating your sequence directly, Pandita’s algorithm is helpful.
There are many algorithms for enumerating permutations and generating the p-th permutation in an enumeration directly. Generating permutations enumerated in lexicographic order is more expensive than generating permutations enumerated using the Fischer-Yates shuffling method.
There are also more exotic orderings for generating permutations such as the “change ringing” permutations devised by bell ringers centuries ago.
There are many algorithms for enumerating combinations as well, and for generating the p-th combination directly.
The study of combinatorics shows that there are structures in the integers you might not have noticed previously. Ordinary decimal notation decomposes numbers between 0 and 10n-1 into a sum of n numbers; we can also do so for numbers between 0 and n!-1, and numbers between 0 and (n C k)-1 for any k. These decompositions have a strong connection to the permutations and combinations of the numbers from 0 to n-1.
FAQ
What is the Cartesian product and how do I compute it for two or more sequences?The Cartesian product of A and B is the set (or sequence) of all pairs (a, b) with a in A and b in B. In C#, you can:
- For two sequences: nest loops or use an extension like IEnumerable<(A a, B b)> CartesianProduct(A, B) that yields pairs lazily.
- For three or more known-at-compile-time sequences: add overloads that return tuples (a, b, c), etc.
- For arbitrarily many sequences of the same element type T: take IEnumerable> and build the product lazily with LINQ by appending each new item (e.g., using an immutable deque’s PushRight) to all partial results.What’s the difference between “eager” and “lazy” Cartesian product implementations?Eager implementations materialize the entire product (e.g., into a HashSet) up front, which can be costly in time and memory for large products. Lazy implementations (yield return) construct items only as the result is iterated, shifting cost to enumeration and often reducing peak memory. Prefer lazy when you stream or filter results and don’t need the whole product at once.How does the Cartesian product relate to representing integers?Taking the Cartesian product of the digit set [0..b−1] with itself n times enumerates all n-digit base-b numbers in lexicographic order. The p-th n-tuple corresponds to the base-b digits of p (zero-padded); conversely, digits map to an index p. This “digits-as-tuples” view generalizes to other index-to-tuple mappings used later for permutations and combinations.
How can I generate permutations in lexicographic order, including when the list has duplicates?Use Pandita’s (Narayana) next-permutation algorithm on a mutable array:
1) Find the rightmost index i where items[i] < items[i+1].
2) Find the rightmost j > i with items[j] > items[i].
3) Swap items[i], items[j].
4) Reverse the suffix after i.
It supports duplicates and yields the next lexicographic permutation; repeat until no next exists.What is the performance of Pandita’s next-permutation algorithm?Space is O(1). Worst-case time per step is O(n) (suffix scan, swap, reverse), but amortized over all n! permutations it averages about 3 comparisons and 1.5 swaps per permutation—i.e., amortized O(1) per permutation with rare O(n) steps.How do I generate the p-th permutation directly (without enumerating all before it)?Use the factorial number system (factorial base). Express p in mixed radix with digits for (n−1)!, (n−2)!, …, 0!. Repeatedly select the r-th remaining element to build the permutation. A typical implementation keeps a “remaining” list [0..n−1], removes at index r each step, and appends to result. Note: List.RemoveAt(r) makes this O(n²); using an immutable deque with O(log n) remove can reduce to O(n log n).How is Fischer–Yates related, and can I map a number to a FY-style permutation?The Fischer–Yates shuffle generates a random permutation by n swaps using random offsets r_i in ranges [0..i]. Interpreting a sequence of r_i as factorial-base “digits” lets you map a number p to a FY-ordered permutation with O(n) swaps, cheaper than lexicographic selection. The ordering differs from lexicographic but is consistent and indexable.What is “change ringing” order and how can I generate it efficiently?Change ringing enumerates permutations so successive ones differ by exactly one adjacent swap. Two methods:
- A recursive InsertAt approach builds columns from smaller permutations (elegant but can be O(n²) to enumerate a single permutation).
- Even’s algorithm maintains directions for each number, repeatedly swapping the largest mobile element and flipping directions of larger elements; it yields O(n) time per permutation and O(n) space.How can I generate all k-combinations of n elements in lexicographic order?Two approaches (using combinations read right-to-left for convenience):
- Iterative next-combination: find the rightmost “increasable” element, increment it, and reset all elements to its left to the lowest possible values. Amortized O(1) per step; yielding a copy is O(k).
- Recursive: first yield combinations not containing n−1, then those that end with n−1 (append n−1). This is O(n) per combination with O(n) recursion depth; uses an immutable deque’s PushRight.What are “combination numbers” and how do I map between a combination and its index?There are “n choose k” (n C k) combinations. Compute n C k efficiently via result = Π_{i=1..k} (n−k+i)/i (using BigInteger; reduce with k = min(k, n−k)). To index:
- Given (n, k, p): recursively decide whether the combo ends with n−1 by comparing p with (n−1 C k), append accordingly.
- Given a sorted combination x0 < x1 < … < x_{k−1}: its index is Σ_i (x_i C i+1). This “combinatorial number system” (Macaulay/Lehmer) doesn’t need n and provides a unique decomposition of p into choose-terms.
pro $24.99 per month
access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
Fabulous Adventures in Data Structures and Algorithms ebook for free
