Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

10 Answers 10

The following web site might be useful to you:

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
    
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! –  Gabe Cunningham Oct 28 '09 at 15:26
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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