Chapter 6: Combinatorial algorithms

Introduction

This chapter introduces algorithms for generating Cartesian products, permutations, and combinations of sequences, and relates their ordered outputs to representations of integers.

• Three combinatorial sequence operations: Describe the three combinatorial operations covered in the chapter: Cartesian products, permutations, and combinations. State what each operation produces from one or more sequences.
  Why it matters: These three operations are the foundation for the generation algorithms developed throughout the chapter.
• Integer positions in generated outputs: Explain why, because each combinatorial operation produces a sequence of sequences, it is meaningful to ask for the pth generated sequence. Describe the chapter's stated connection between answering that question and decomposing integers into sums of smaller integers.
  Why it matters: Indexing a generated result connects practical enumeration algorithms to useful ways of representing integers.
• Practical generation motivation: State the practical motivation given for permutation and combination generators: they are useful for rapidly generating test cases, despite not typically being supplied by the .NET base-class library.
  Why it matters: The motivation shows why these classic algorithms are useful to programmers as well as mathematically interesting.

Key terms: Cartesian product, permutations, combinations, sequences, pth sequence, decomposed into sums, factorial base representation, combinatorial base representation, .NET, base-class library

6.1 The Cartesian product

Introduces the Cartesian product as the meaning behind iterating over every character–weapon pairing and previews ways to compute it.

• Cartesian product definition: Explain the Cartesian product of two sets A and B as the set of every possible ordered pair whose first item comes from A and second item comes from B.
  Why it matters: This gives a mathematical name to the all-pairs operation that later algorithms compute.
• All-pairs iteration meaning: Describe how nested foreach loops or multiple from clauses in a C# query expression iterate over the Cartesian product when they consider every character with every weapon. Distinguish this semantic all-pairs purpose from the loop mechanism used to implement it.
  Why it matters: Naming the operation makes code and algorithms easier to describe in terms of what they produce rather than how they loop.

Key terms: Cartesian product, A×B, ordered pair, nested loop, foreach, query expression, from clause, CROSS JOIN

6.1.1 The Cartesian product of a few sets or sequences

This section develops Cartesian-product extension methods for fixed numbers of sets or sequences, progressing from pair tuples to lazy sequence products and projected results.

• Pair Cartesian product: Explain that the Cartesian product of two sets contains every two-item tuple formed by choosing one item from each set, and describe its implementation as the abstraction of nested iteration.
  Why it matters: Cartesian products provide a systematic way to enumerate every possible pairing of choices.
• Tuple nesting and arity: Describe why applying the two-set CartesianProduct method again to a prior product creates a nested pair, and distinguish that result from a direct three-set product that returns three-valued tuples.
  Why it matters: Recognizing tuple shape prevents confusing output types and motivates fixed-arity overloads.
• Sequence product laziness: Explain why CartesianProduct can accept arbitrary sequences rather than only sets, including that duplicate input values may yield duplicate output tuples, and distinguish the lazy sequence implementation from the eager hash-set implementation.
  Why it matters: A lazy product can avoid constructing a large collection of combinations until its results are actually needed.
• Projected product results: Describe the Cartesian-product overload that accepts a function of the selected values, explaining that it combines CartesianProduct with Select so callers can directly produce useful results instead of intermediate tuples.
  Why it matters: Projection makes product code more fluent when pairs are only temporary holders for values used together.

Key terms: Cartesian product, set, tuple, extension method, nested pairs, two-item tuple, three-valued tuple, CartesianProduct, sequence, HashSet<T>

6.1.2 The Cartesian product of arbitrarily many sequences

This section derives a lazy Cartesian-product algorithm for any number of same-typed sequences by progressively extending immutable deque prefixes.

• Arbitrary-product type signature: Explain why an arbitrary Cartesian product takes a sequence of sequences and returns a sequence of sequences rather than tuples. State that, because the number of input sequences is known only at runtime, every input and output element must share one type.
  Why it matters: The method’s types must represent a result whose length cannot be fixed at compile time.
• Zero-sequence product identity: Describe the Cartesian product of zero and one input sequences, and trace how the algorithm builds a product one input sequence at a time. Explain that the initial product is one empty sequence, then each new input item is appended to every existing partial result.
  Why it matters: Starting with one empty result makes the same expansion rule work uniformly for zero, one, or many input sequences.
• Lazy query construction: Explain that the implementation constructs nested query objects rather than immediately enumerating the Cartesian product. State that building the query for n input sequences costs O(n) time and space, while enumerating each produced result costs O(n) because it creates an n-item deque with amortized O(1) pushes.
  Why it matters: Laziness defers the potentially large cost of producing combinations until a caller actually iterates the query.
• Lexicographic output order: State that when all input sequences are sorted, this algorithm generates the output sequences in lexicographic, or dictionary, order.
  Why it matters: The ordering property motivates the next connection between sorted numeric products and the integers.

Key terms: sequence of sequences, tuples, fixed size at compile time, extension method, Cartesian product, zero-element sequence, PushRight(), immutable deque, query expression, fully lazy

6.1.3 The connection to the integers

This section connects repeated Cartesian products to positional integer representations and introduces permutations as the operation for reordering a sequence.

• Cartesian products as digit strings: Explain how the Cartesian product of the digit sequence 0 through 9 with itself n times generates every n-digit decimal string in lexicographic order. Relate each generated tuple to a number from 0 through 10^n minus 1, including strings with leading zeroes.
  Why it matters: This connection shows that Cartesian products systematically enumerate positional representations, not just arbitrary tuples.
• Positional bases and tuple ordering: Describe positional notation as decomposing an integer into digits weighted by powers of the base, such as A×10^3 + B×10^2 + C×10 + D. State that the same Cartesian-product idea applies to hexadecimal, octal, binary, and other bases, and that the product preserves the input sequences' ordering in its tuples.
  Why it matters: Seeing digits as ordered choices with place-value weights makes the link between number systems and combinatorial enumeration explicit.
• Permutations as sequence reordering: Distinguish the Cartesian product's role in exploring tuples from independent sequences from the role of permutation in reordering a single sequence. State that permutations are the next combinatoric operation introduced for the reordering task.
  Why it matters: Choosing the right combinatoric operation prevents treating sequence rearrangement as though it were a product of independent choices.

Key terms: Cartesian product, lexicographic order, n-digit strings, decimal notation, base, place value, powers of 10, hexadecimal, octal, permutation

6.2 Permutations

This section introduces permutations as sequence reorderings, explains their factorial growth and uses, and shows how integer permutations can reorder lists of any type.

• Permutation definition and uses: Explain that a permutation is a reordering of a finite sequence, and describe its uses for generating operation-order test cases, shuffling, or reordering items such as songs.
  Why it matters: Permutations let a program systematically or randomly explore different orders of the same items.
• Factorial permutation count: Describe why an n-element sequence with distinct elements has n! permutations: there are n choices for the first position, then n−1 for the second, and so on, so enumerating them has O(n!) growth.
  Why it matters: The factorial number of possible orders explains why generating every permutation quickly becomes impractical.
• Index-based list permutation: Describe how a permutation of the integers 0 through n−1 can permute a list of arbitrary items by treating each integer as an index and returning a new list in that indexed order, without changing the original list.
  Why it matters: Generating integer orderings once makes permutation algorithms applicable to cards, strings, tests, and other item types.

Key terms: permutation, reordering, shuffling, n factorial, n!, O(n!), distinct elements, indices, items, original list

6.2.1 Lexicographic permutations with repetitions

This section presents Pandita’s in-place next-lexicographic-permutation algorithm and an algorithm for directly generating a numbered lexicographic permutation of distinct integers.

• Pandita’s next-permutation algorithm: Describe how Pandita’s algorithm transforms a mutable permutation into the next lexicographic permutation: find the rightmost item immediately left of a larger item, swap it with the rightmost larger item, and reverse the suffix. State that no next permutation exists when the sequence is in reverse order.
  Why it matters: This provides an efficient way to enumerate permutations in dictionary order without generating duplicates for repeated values.
• Repeated-element permutation enumeration: Explain why starting in sorted order and repeatedly applying NextLexiPermutation lists permutations in dictionary order, including when the input contains duplicate elements. State that the algorithm mutates the sequence in place.
  Why it matters: It identifies a practical enumeration method for multisets, where naïvely permuting positions can produce duplicate results.
• Permutation successor performance: State that the next-permutation algorithm uses O(1) extra space and has O(n) worst-case time, but amortized O(1) time when enumerating all permutations of unique items. Explain that most calls only inspect the final pair and do little work, while expensive suffix scans and reversals are rare.
  Why it matters: Amortized analysis shows why an algorithm with occasional linear operations can still be cheap per generated permutation overall.
• Direct permutation-number generation: Trace how to generate permutation number p of the distinct integers 0 through n−1 without enumerating earlier permutations: divide p by (n−1)! to choose the first remaining item, use the remainder as the rank within that row, and repeat on the remaining items. State that permutation numbers range from 0 through n!−1.
  Why it matters: This unranking method directly accesses a chosen lexicographic permutation and exposes the recursive structure behind permutation numbers.
• Direct-generation cost limits: Describe the major costs of the direct permutation-number algorithm: creating the remaining list is linear, naïve List RemoveAt is called n times and yields O(n²) total cost, and arbitrary-size factorial, division, and modulus operations are not necessarily constant time. Explain that a deque with O(log n) indexed removal could reduce the removal total to O(n log n).
  Why it matters: This prevents treating high-level list and BigInteger operations as free when analyzing an otherwise simple unranking algorithm.

Key terms: lexicographic ordering, Pandita’s algorithm, NextLexiPermutation, mutable array, duplicates, repetitions, lexicographic permutations, O(1) space, O(n) worst case, amortized O(1)

6.2.2 The factorial base representation of permutation numbers

This section shows how a permutation number can be written in factorial base and decoded into its corresponding lexicographic permutation.

• Factorial base notation: Explain how a permutation number is decomposed into factorial-base digits, where each digit multiplies a factorial rather than a power of ten. State the digit constraint: the digit in position i from the right ranges from 0 to i, so the rightmost digit is always 0.
  Why it matters: Factorial base gives a direct numeric representation for indexing permutations.
• Permutation decoding procedure: Describe how to turn factorial-base digits for a permutation number into the corresponding permutation: begin with the remaining numbers 0 through n−1, then process digits left to right by removing the item at each digit's index and appending it to the result.
  Why it matters: This procedure converts a compact permutation number into an explicit ordering without generating all permutations.
• Remainders as factorial digits: Trace the connection between the lexicographic permutation algorithm's successive remainder values and factorial-base digits, using examples such as 9 becoming 1110 and 19 becoming 3010.
  Why it matters: It explains why the permutation-selection indices naturally have the ranges required by factorial base.

Key terms: factorial base notation, permutation number, factorial base digit, remaining list, result list, lexicographic permutation, GetLexiPermutation, r

6.2.3 The Fisher–Yates shuffling algorithm

This section presents the Fisher–Yates method for randomly shuffling a mutable list and relates its random choices to a cheaper, nonlexicographic permutation numbering.

• Fisher–Yates shuffle process: Describe how the Fisher–Yates algorithm randomly permutes a mutable list: it generates bounded random values and uses them to perform n swaps among list positions. State that the result can be any ordering of the original items.
  Why it matters: Fisher–Yates provides a fast practical way to produce a fair shuffle rather than merely listing permutations.
• Factorial-base shuffle numbering: Explain that the sequence of random values used by Fisher–Yates can be read as factorial base digits of a permutation number. Describe that numbering permutations this way produces a Fisher–Yates ordering that is similar to, but not the same as, lexicographic ordering.
  Why it matters: This connection lets a permutation number drive the same efficient swap-based construction used for shuffling.
• Swap-based performance advantage: Justify why the Fisher–Yates permutation technique is cheaper than lexicographic generation when lexicographic order is unnecessary: it performs n O(1) swaps rather than O(n) RemoveAt() operations. State that lexicographic order remains useful when its natural ordering is wanted, while Fisher–Yates is useful for a fast fair shuffle.
  Why it matters: Choosing the ordering you actually need can avoid the more expensive removal-based permutation construction.

Key terms: Fisher–Yates algorithm, shuffle, mutable list, swap, factorial base, permutation number, Fisher–Yates permutation, lexicographic ordering, nonlexicographic ordering, O(1)

6.2.4 A recursive change-ringing algorithm

This section develops a recursive change-ringing order for permutations, shows how to generate either all changes or one indexed change, and analyzes the cost of the lazy implementation.

• Change-ringing permutation constraint: Explain the change-ringing problem as enumerating all n! permutations of n distinct bells so that each successive permutation differs by exactly one swap of consecutive bells. Distinguish this required ordering from ordinary lexicographic permutation order, which can violate the one-adjacent-swap rule.
  Why it matters: Change-ringing imposes a structural relationship between neighboring permutations, not merely a requirement to list every permutation.
• Recursive table construction: Describe the recursive construction of change-ringing permutations: start with the permutations of n−1 bells, arrange copies in n rows and (n−1)! columns, and insert the new largest bell n−1 at positions determined by the row. Explain that columns alternate insertion direction, right then left, and are read top to bottom.
  Why it matters: The alternating insertion directions are what make the recursive enumeration preserve the one-adjacent-swap relationship.
• Permutation-number change lookup: Trace how to generate one change-ringing permutation directly from permutation number p between 0 and n!−1: compute column c as floor(p/n), recursively generate change c for n−1 elements, compute row p mod n, and insert n−1 from the right for an even c or from the left for an odd c. State that the n=0 base case returns the empty permutation.
  Why it matters: Direct lookup lets the program produce a requested change without first enumerating every earlier permutation.
• Lazy generation performance: Explain why calling the lazy single-permutation generator can appear to cost O(1) before enumeration, but fully enumerating its n elements is worst-case O(n²). Relate the quadratic cost to up to n nested lazy InsertAt calls per output element, and state that an O(log n) immutable-deque InsertAt would reduce this to O(n log n) per permutation.
  Why it matters: It separates the cost of constructing a lazy sequence from the real cost of consuming all of its values.

Key terms: change-ringing, permutations, swap of consecutive bells, lexicographic ordering, recursive change-ringing algorithm, n rows, (n−1)! columns, column direction, insert, from the right

6.2.5 Even’s change-ringing algorithm

This section presents Even’s iterative algorithm for generating every permutation in change-ringing order, including its mutable implementation safeguards and linear per-permutation cost.

• Even’s change-ringing procedure: Describe how Even’s algorithm generates the next change-ringing permutation using directions and mobile numbers. State that it repeatedly moves the largest mobile number, reverses directions of all larger numbers, and stops when no mobile number exists.
  Why it matters: This is the section’s main method for enumerating all permutations in change-ringing order without recursive generation.
• Mobile-number definition: Explain what makes a number mobile in a directed permutation: the immediately adjacent number in its assigned direction must be smaller. Distinguish this from merely being next to another number or pointing toward a boundary.
  Why it matters: Correctly identifying mobile numbers is what makes each step of Even’s algorithm choose the right adjacent swap.
• Mutable-array iterator safety: Describe the implementation’s two mutable arrays: one holds the current permutation and the other stores each number’s direction, represented by 1 for right and −1 for left. Explain why the algorithm copies the permutation with ToList before yielding it.
  Why it matters: Copying before yield prevents later iterator mutations from changing a permutation already handed to the caller.
• Linear performance analysis: State that this implementation takes O(n) time per yielded permutation and O(n) extra storage for each yielded copy. Justify the time bound by identifying the linear copy, full search for the largest mobile number, and worst-case direction-update loop, while swaps are O(1).
  Why it matters: The linear bound explains why Even’s method improves on the recursive implementation’s potentially quadratic work per permutation.

Key terms: Even’s change-ringing algorithm, change-ringing order, mobile number, largest mobile number, direction, mobile, left, right, mutable arrays, permutation

6.3 Combinations

This section introduces combinations as order-preserving k-item subsequences, shows how index combinations apply to arbitrary lists, and previews ways to enumerate or directly generate them.

• Combination definition: Describe a combination of a sequence of length n as a subsequence of length k that preserves the original item order while omitting some items, using an example such as the length-3 combinations of ABCDE.
  Why it matters: This definition distinguishes the objects that combination algorithms must generate from reordered sequences.
• Index-based list combinations: Explain that combinations can be generated once as k-item subsequences of the indices 0 through n−1 and then used to select corresponding items from any list of length n. Describe how an index combination such as [1, 2] selects the items at those positions from another list.
  Why it matters: Generating index patterns separately makes a combination algorithm work for lists containing any element type.
• Combination algorithm roadmap: State that the following subsections will cover lexicographic enumeration, a mutation-free recursive enumeration method producing the same result, and methods for directly generating the p-th combination through a nonstandard integer decomposition.
  Why it matters: The roadmap helps distinguish algorithms that list every combination from algorithms that jump directly to one requested combination.

Key terms: combinations, subsequences, n, k, indices, k-item subsequence, 0, …, n−1, combination, lexicographic algorithm, Pandita’s algorithm

6.3.1 Lexicographic combinations with a twist

This section shows how to enumerate combinations in right-to-left lexicographic order using either an in-place successor algorithm or an immutable recursive algorithm.

• Right-to-left combination ordering: Explain why increasing-integer sequence notation makes the section enumerate combinations in lexicographic order from right to left, and describe that combinations are ordered by their rightmost elements first.
  Why it matters: This ordering is the basis for both combination-generation algorithms and for later indexing of combinations.
• Mutable lexicographic successor: Describe how to produce the next combination by finding the rightmost increasable element, incrementing it, and resetting every element to its left to its lowest possible value. State what happens when no element is increasable.
  Why it matters: This gives an iterative way to enumerate every valid combination exactly once in the required order.
• Combination edge cases and cost: State that requesting k greater than n yields no combinations, while k equal to zero yields one empty combination, and describe the iterative method's output cost as O(k) because it copies the current combination.
  Why it matters: Edge cases determine whether an enumerator has the correct mathematical behavior, while output copying explains its practical per-result cost.
• Immutable recursive enumeration: Explain the recursive split that first generates combinations not containing n−1 and then combinations ending in n−1, using right-end insertion to preserve the right-to-left lexicographic order. Describe its worst-case O(n) time and O(n) stack-space characterization per generated combination.
  Why it matters: The recursive version demonstrates a nonmutating way to generate the same ordered results and connects the algorithm to the immutable deque.

Key terms: lexicographic order, right-to-left ordering, combination, bit strings, increasing integers, NextLexiCombination, Increasable, Combinations1, lexicographic combination, ToList()

6.3.2 Counting combinations

This section defines and efficiently computes binomial coefficients, then uses them to map lexicographic combination numbers back to combinations recursively.

• Choose operator identities: Explain what n C k counts and state its key identities: impossible and empty choices, symmetry, Pascal-style recurrence, and the direct factorial-based formula.
  Why it matters: These identities let you count combinations and split the space of combinations into manageable parts.
• Efficient Choose computation: Describe how to compute n C k efficiently by first using symmetry to replace k with the smaller of k and n-k, then iteratively applying n C k = (n C (k-1))(n-k+1)/k with multiplication before division.
  Why it matters: This avoids needlessly large BigInteger intermediates while calculating combination counts.
• Choose performance bounds: State that the iterative Choose method takes k loop iterations, is best-case O(k), and can be O(n log n) in the worst case when k is n/2 because BigInteger operations grow more expensive with operand size.
  Why it matters: The cost of counting combinations affects the performance of algorithms that repeatedly call Choose.
• Recursive combination unranking: Describe how a combination number p from 0 through (n C k)-1 identifies one lexicographically ordered combination by recursively determining whether it lies in the block that omits or includes n-1, subtracting the size of an earlier block when entering the later block, and appending n-1 when it is included.
  Why it matters: Unranking makes it possible to generate a particular combination directly, including a random combination selected through a random index.

Key terms: Choose operator, n C k, n choose k, empty combination, lexicographic order, BigInteger, Choose, n C k = n C (n-k), n C k = (n C (k-1))(n-k+1)/k, compound assignment operator

6.3.3 The combinatorial base representation of combinations

This section derives a direct combinatorial-base formula for finding a combination’s position in the ordered list of combinations.

• Combination index formula: State how to compute the combination number of a k-element combination x0, x1, …, xk−1: sum x0 C 1, x1 C 2, …, and xk−1 C k. Explain that this sum gives the combination's index in the book's lexicographic ordering.
  Why it matters: The formula converts a combination directly into its numeric rank without enumerating all earlier combinations.
• Rank derivation by rightmost elements: Explain why each element contributes a binomial-coefficient offset by considering the rightmost element first, then fixing and removing trailing elements. Use the example 0245 to trace the offsets 5 C 4, 4 C 3, 2 C 2, and 0 C 1, which total 10.
  Why it matters: This reasoning shows why the direct formula correctly counts the combinations skipped before the target combination.
• Direct algorithm advantages and cost: Describe how the direct list-based method computes the sum without recursion, popping deques, or knowing n. State that it calls Choose k times, has best-case O(k²) and worst-case O(n² log n) performance when n is bounded by the largest combination element, and could memoize Choose to trade memory for speed.
  Why it matters: The direct method is simpler than the recursive version, while its cost explains when caching binomial coefficients may help.
• Combinatorial base representation: Explain the deeper claim that every number p has a unique decomposition into k combinatorial-base components of the form x0 C 1 + … + xk−1 C k, corresponding to one k-element combination. State that this is called the Macaulay representation, while the ranking application is credited to D. H. Lehmer.
  Why it matters: The representation explains why combinations and integer ranks can be converted uniquely in both directions.

Key terms: combination number, lexicographic order, Choose, combinatorial base, rightmost number, combination, BigInteger, memoize, recursion, deque

6.4 Summary

This summary recaps algorithms for Cartesian products, permutations, and combinations, along with their connections to integer representations.