6 Combinatorial algorithms

Combinatorial algorithms are presented as practical tools for working with finite discrete structures, with a recurring theme that seemingly simple sequence operations can reveal deeper facts about how integers are represented and decomposed. The chapter begins by treating the Cartesian product as a systematic way to combine sequences into tuples, showing how nested loops, query expressions, and small helper methods can make the code clearer while preserving the same underlying behavior. It also emphasizes the tradeoff between eager and lazy evaluation, since building all combinations up front can be costly when the product is large.

The discussion then moves to permutations, first showing how to apply a permutation to any list and then exploring several ways to generate permutations in order. Lexicographic permutation generation is based on a classic next-permutation algorithm that mutates a list in place, has O(1) amortized cost per permutation, and connects naturally to factorial-base notation, where each permutation number is decomposed into factorial place values. The chapter also presents a direct method for generating the p-th permutation, contrasts lexicographic ordering with a cheaper Fisher–Yates-based ordering, and introduces a recursive change-ringing approach that generates permutations by inserting the next largest element in alternating directions.

Finally, the chapter turns to combinations, where order is preserved and only subsequences of a given size are selected. It presents lexicographic generation by mutating the current combination, a clean recursive generator that builds combinations by including or excluding the largest element, and methods for counting combinations using the choose operator. From there, it shows how to map between a combination and its index in lexicographic order, revealing a combinatorial-base decomposition closely related to the Macaulay representation. Across all of these topics, the chapter highlights not only how to generate and rank combinatorial objects, but also how algorithm choice affects readability, laziness, and performance.

• The basic combinatoric operations on finite sequences—the Cartesian product, enumeration of permutations, and enumeration of combinations—typically aren’t supplied by standard libraries, but they’re 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. Adding a projection function at the end instead of returning a tuple is also quite useful.
• To compute the Cartesian product of n sequences, where n is known only 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 directly generating the p-th permutation in an enumeration. Generating permutations enumerated in lexicographic order is more expensive than generating permutations enumerated using the Fisher–Yates shuffling method.
• More exotic orderings for generating permutations exist, such as the change-ringing permutations devised by bell ringers centuries ago.
• There are also many algorithms for enumerating combinations and for generating the p-th combination directly.
• The study of combinatorics shows that the integers contain structures you may not have noticed previously. Ordinary decimal notation decomposes numbers between 0 and 10ⁿ−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 are strongly connected to the permutations and combinations of the numbers from 0 to n−1.

FAQ