Algorithmic Combinatorics resources?

Question

Some branches of combinatorics lend themselves naturally to algorithms; graph theory is a natural example. However, straight-up enumerative combinatorics relies much more on analytic and algebraic methods. As a result, you often don't have any idea of how you could systematically generate the objects you want. In order to do so with a computer, you'd need to pick a "nice" encoding, impose a total order on the coded objects, and then generate them one-by-one, checking against previous ones for whatever equivalence you're concerned with. Burnside's or Polya's Theorem will tell you when you've found them all, but in the meanwhile, you want an encoding and an order that's easy to work with, and that generates successive objects fairly quickly.

Are there any good resources for this sort of algorithmic combinatorics? I'd like something that's not tailored to just a specific problem, unless that problem is representative of a large class of problems. Essentially, I'd like to know some particularly useful encodings and some useful generation algorithms. (For instance, for some problems, it might be more efficient to generate the objects randomly instead of using a total order).

Answer 1

Knuth: The Art of Computer Programming, volume 4 (fascicles). It is really comprehensive (but the algorithm descriptions are not easy to read).

Also you may be interested in the theory of combinatorial species (look it up on wikipedia; this system does not allow me to include more than 1 hyperlinks, which I find pretty stupid to be honest...).

Answer 2

The following web site might be useful to you:

The Stony Brook Algorithm Repository, http://www.cs.sunysb.edu/~algorith/

Answer 3

Another one of the classical books in this area is Combinatorial Algorithms by Nijenhuis and Wilf (1978).

Answer 4

Another book is Classification Algorithms for Codes and Designs by Kaski and Östergård. The authors are responsible for the recent complete enumeration of Steiner triple systems of order 19. (All 11 billion of them!)

Answer 5

Here's an article available online: "Isomorph-free exhaustive generation" by Brendan D. McKay.

See cs.anu.edu.au/~bdm/papers/orderly.pdf

The author also wrote the graph isomorphism package 'nauty' which is one of the main tools of the trade.

Answer 6

The method of coupling from the past can be used to sample uniformly at random from certain distributions. Here is a simple demonstration which illustrates the method, and here it is in action computing random Aztec diamond tilings.

Answer 7

I suggest Reverse Search for Enumeration (Avis and Fukuda, Discrete Applied Mathematics, 1996). Essentially, whenever you have a way of canonically reducing a combinatorial object to a simpler one of the same type, you have an enumeration algorithm. It does not need a definition of a total ordering (or rather, a total ordering falls out of the enumeration algorithm rather than being something you define a priori) and like the McCay method already mentioned above it does not need to check against all previously generated objects, so it can be highly efficient.

Answer 8

The book Algorithmic Combinatorics by Shimon Even is a bit old (1973) but describes many of the fundamental methods in the field (encoding, efficient generation and sampling of permutations, combinations, etc.)

Answer 9

There's an entire book Combinatorial Generation on this subject by Frank Ruskey that's available online.

Answer 10

a key ingredient in modern software like mathematica is using hypergeometric functions. Let me recall the Knuth's statement in his Concrete Mathematics... "with hypergeometric functions you are likely to embrace each elementary functions studied in a technological career"... well, sort of

Answer 11

I have often turned to Combinatorial Algorithms: Generation, Enumeration, and Search by Donald L. Kreher and Douglas R. Stinson when I have needed to implement a basic combinatorial algorithm.