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
  • the deep connection between these three combinatoric operations and ways to decomposing integers into sums

Combinatorics is today a broad field of mathematics, covering everything from graph theory to optimization theory, but the common thread running through it all is that we are interested in algorithms for solving problems involving a finite number of discrete elements, such as a sequence of n integers. In this chapter we’ll cover three of the basic combinatoric operations on sequences.

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

6.2.2 The factorial base representation of permutation numbers

6.2.3 The Fischer-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

6.4 Summary