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).
No comments:
Post a Comment