This chapter surveys practical, elegant algorithms for three foundational combinatorial operations on finite sequences—Cartesian products, permutations, and combinations—and shows how treating their outputs as sequence-of-sequences naturally leads to “what is the p‑th result?” indexing problems. Along the way, it connects enumeration orders to number systems: decimal digits for repeated Cartesian products, factorial-base (Lehmer code) for permutations, and a combinatorial-base (Macaulay/Lehmer) representation for combinations. The discussion is grounded in real programming practice (C#/.NET idioms, lazy vs. eager evaluation, and small, fluent helpers), with an emphasis on readability, performance, and test‑case generation.
For Cartesian products, the chapter starts from nested loops and builds up reusable extensions for pairs, triples, and ultimately an arbitrary number of input sequences by treating the input as a sequence of sequences. The arbitrary‑arity product is expressed compactly with query expressions or aggregation, uses an immutable deque’s PushRight to avoid mutation, and preserves input order so results appear in lexicographic order when inputs are sorted. This ordering directly mirrors positional notation: taking a product of digits with itself n times enumerates all n‑digit numbers in order, reinforcing the link between enumeration schemes and integer decompositions.
Permutation techniques range from Narayana Pandita’s classic next‑lexicographic algorithm (supports duplicates, amortized O(1) per step) to direct generation of the p‑th permutation via factorial‑base digits, to the Fischer–Yates shuffle for uniform random reordering and its closely related p‑th, non‑lexicographic mapping. The chapter also presents “change ringing” orderings: a simple recursive construction and Even’s efficient O(n)‑per‑permutation algorithm that swaps exactly one adjacent pair between successive permutations. For combinations, it shows how to apply index sets to any data, provides both a right‑to‑left next‑lexicographic mutating method and a clean recursive, non‑mutating generator, and develops efficient computation of n choose k. Finally, it covers ranking and unranking: generating the p‑th combination and computing a combination’s index using the combinatorial‑base sum Σ (x_i choose i+1), highlighting performance trade‑offs and practical strategies (laziness, memoization, and suitable data structures) throughout.
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 can I generate it for two or more sequences?The Cartesian product of sequences A and B is the set (or sequence) of all pairs (a, b) with a in A and b in B. In code it’s just two nested loops. You can wrap that as an extension that returns IEnumerable of tuples to make it read like a sequence operation, and even add a projection overload that takes a Func<A,B,R> so you produce results directly. For three inputs, add a third nested loop (or a 3-arity overload); for more inputs, see the “arbitrarily many sequences” approach.How do I compute the Cartesian product of arbitrarily many sequences?Accept a sequence-of-sequences: IEnumerable<IEnumerable<T>>. Treat the product of zero sequences as one empty sequence [[ ]], then iteratively “append” each element of the next input sequence to each partial result. You can express this with LINQ using Aggregate and an immutable deque’s PushRight to avoid mutation. The construction is fully lazy, preserves input order (lexicographic), and costs O(n) to build the query for n input sequences; enumerating each result sequence costs O(n).When should I use a lazy vs eager Cartesian product implementation?Eager (building a HashSet or list) constructs all tuples up front, using O(|A|·|B|) space and time immediately; it’s handy if you need random access, deduplication, or repeated membership tests. Lazy (yielding tuples) defers work and memory until enumeration and is preferable when the product is large, you’ll stream/short-circuit, or you don’t need the whole result at once.What are permutations and how many are there?A permutation is a reordering of all elements of a sequence. For n distinct items there are n! (factorial) permutations, which grows very quickly. You can permute “any” list by generating a permutation of indices 0..n-1 and applying those indices to the list.How do I get the next permutation in lexicographic order (handles duplicates)?Use Pandita’s (next_permutation) algorithm: (1) find the rightmost index i with a[i] < a[i+1]; if none, you’re at the last permutation. (2) find the rightmost j with a[j] > a[i]. (3) swap a[i], a[j]. (4) reverse the suffix a[i+1..end]. It works with duplicates, runs in-place, has amortized O(1) time per permutation (worst case O(n)), and generates permutations in dictionary order.How can I generate the p‑th lexicographic permutation directly?Use the factorial-base (Lehmer code) method: maintain a list of remaining numbers [0..n-1]. For cur = n..1, divide p by (cur-1)! to get digit r, select remaining[r], append it, remove it, and set p = p % (cur-1)!. This avoids enumerating all prior permutations. Beware that removing from a List is O(n); for large n use a structure with O(log n) remove (e.g., an immutable deque/split) to get O(n log n) overall.What is Fisher–Yates shuffling, and how does it relate to permutation numbers?Fisher–Yates picks random r_i in [0..i] and swaps position i with i+r_i for i from 0..n-1, yielding an unbiased random permutation in O(n). The r_i act like factorial-base digits of a permutation number in a non-lexicographic ordering. You can also map a given p to the “p-th” Fisher–Yates-style permutation using the same digits and swaps in O(n).What is “change ringing” permutation order, and how can I generate it efficiently?Change ringing lists all permutations so that each consecutive pair differs by exactly one adjacent swap. A recursive “insert-at” construction yields this order but can be O(n²) per permutation when enumerated. Even’s algorithm is an O(n)-per-permutation in-place method: track a direction (left/right) for each number, repeatedly swap the largest “mobile” number with its neighbor in its direction, then reverse directions of all larger numbers. When yielding results, copy before returning to avoid exposing mutable state.What are combinations, how many exist, and how do I compute n choose k efficiently?Combinations are k-length subsequences (indices increasing) of 0..n-1; order is preserved and elements aren’t reordered. There are n C k combinations. Compute n C k iteratively and stably using result = result * (n-k+i) / i for i=1..k with k = min(k, n-k) to keep numbers small; this avoids large intermediates and runs in O(k) BigInteger ops (worst-case about O(n log n)).How do I map between a combination number p and its combination, and what is the “combinatorial number system”?Recursive mapping: first (n-1 C k) combinations don’t end with n-1; the rest do—so compare p with that boundary to recurse and optionally append n-1. The inverse (index of a combination x0<x1<…<xk-1) is p = Σ_{i=0..k-1} (xi C (i+1)); this “combinatorial base” (Macaulay/Lehmer) representation doesn’t require knowing n and lets you pick a random combination by choosing random p in [0, n C k - 1] and decoding.
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
