chapter six

6 Combinatorial algorithms

 

This chapter covers

  • Generating the Cartesian product of two, three, or arbitrarily many sequences
  • Generating all the permutations (reorderings) of a sequence
  • Generating all the combinations (subsequences) of a sequence
  • Decomposing the integers into sums accordingly

Combinatorics is now a broad field of mathematics, covering everything from graph theory to optimization theory. But the common thread running through it is our interest in algorithms for solving problems that involve a finite number of discrete elements, such as a sequence of n integers. In this chapter, we’ll cover three basic combinatorial operations on sequences:

  • The Cartesian product takes two sequences and produces all the pairs of elements from both sequences. We’ll extend that operation to handle multiple sequences and finally give a concise expression for the Cartesian product of an arbitrary collection of sequences.
  • The permutations of a sequence are all the possible reorderings of all elements of the sequence. We’ll look at several algorithms for producing permutations that use different techniques. Some of these algorithms go back centuries and have elegant properties.
  • The combinations of a sequence are all the subsequences we can create without reordering the sequence. We’ll look at algorithms for producing combinations.

6.1 The Cartesian product

6.1.1 The Cartesian product of a few sets or sequences

6.1.2 The Cartesian product of arbitrarily many sequences

6.1.3 The connection to the integers

6.2 Permutations

6.2.1 Lexicographic permutations with repetitions

6.2.2 The factorial base representation of permutation numbers

6.2.3 The Fisher–Yates shuffling algorithm

6.2.4 A recursive change-ringing algorithm

6.2.5 Even’s change-ringing algorithm

6.3 Combinations

6.3.1 Lexicographic combinations with a twist

6.3.2 Counting combinations

6.3.3 The combinatorial base representation of combinations

Summary