10
$\begingroup$

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).

$\endgroup$

10 Answers 10

5
$\begingroup$

The following web site might be useful to you:

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

$\endgroup$
5
$\begingroup$

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...).

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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!)

$\endgroup$
  • $\begingroup$ Chapter 4 in this book is exactly the sort of thing I'm looking for. Many of the other answers provide good resources to the classical problems of exhaustively generating all the k-subsets of an n-set, or the partitions of n, and so on. Those are nice, but what I'm really looking for is a more general discussion. I think I'll see if my library has this book! $\endgroup$ – Gabe Cunningham Oct 28 '09 at 15:26
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

The book 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.)

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.