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

I have a simple application of Polya's enumeration theorem to counting nonisomorphic pentago boards with a given number of stones. In terms of the theorem, the color generating function is $f(x) = 1+x+y$ corresponding to empty, black, or white, there are $6 \times 6 = 36$ beads, and the group is $Z_4^4 \rtimes D_4$ of size 2048. This all works well.

Next I want to explicit generate a set of representative instances, one from each isomorphism class, without generating all instances and reducing. Is there an analogue of Polya's theorem that would assist in explicit enumeration of instances?

If necessary I can do this by manually unwrapping the structure of my particular group, but am curious if there is a more abstract technique applicable to arbitrary groups.

share|improve this question
    
A related but more powerful version would be to construct an efficient random access enumeration of nonisomorphic instances. I.e., an efficient function $f:Z_{|S|} \to S$, where S is a set of representatives of equivalence classes. –  Geoffrey Irving Apr 15 '12 at 18:44
3  
There is some discussion of this question in Chapter 4 of the book Combinatorics for Computer Science by Gill Williamson. On page 144 it says "Pólya enumeration theory is not generally a good tool for actually listing the system of representatives ..." –  Richard Stanley Apr 15 '12 at 18:59
    
My guess is that such a coding function is possible for any group which can be fully decomposed into small pieces in some sense. It certainly isn't for all groups, including $S_n$, and the fact that $S_n$ contains a huge simple group might explain why. –  Geoffrey Irving Apr 15 '12 at 19:08
    
Richard: Thanks, I was afraid of that. I'll take a look at Williamson's book. I am curious of there's a large class of groups for which efficient random access enumeration functions can be defined, but I suppose that's a separate question. –  Geoffrey Irving Apr 15 '12 at 19:14

1 Answer 1

up vote 3 down vote accepted

There are two very general methods for this type of problem, called orderly generation, and generation by canonical construction path. One place that describes these is the book Classification Algorithms for Codes and Designs by Karski and Östergård (where they call the second method "canonical augmentation"). The second method would certainly work for this, and maybe the first as well.

However, in this case you have quite a small group and a more brutal approach should be faster if coded carefully. Define some (lexicographic-type) order on all boards. Then find those boards which are mimimal in their equivalence class according to that order. The crudest way is to generate all boards and reject those which are mapped by a group element to a smaller board; this is easily feasible for your problem. However, by defining the order carefully, you should be able to do much better than that. For example, define the order so that each of the four sub-boards of a minimal board are also in some minimal form (according to some ordering of the set of sub-boards), then make all the minimal sub-boards in advance. Then for each set of four minimal sub-boards, throw it out if it isn't minimal overall.

[Added:] Thinking about this a bit more: There are about 5000 equivalence classes of sub-board; make them all anyhow. Then you just need to select four of these in inequivalent ways according to the action of $D_8$. The inequivalent boards with four inequivalent sub-boards are the tuples $(A,B,C,D)$, $(A,C,D,B)$ and $(A,D,B,C)$ with $A\lt B\lt C\lt D$; i.e., coset representatives of $D_8$ in $S_4$. Then there more types but much smaller counts where some of the sub-boards are equivalent.

share|improve this answer
    
Yeah, I'm using the lexicographic explicit approach elsewhere. It definitely works, but definitely isn't elegant for generation (the nastiest part is dealing with the various different ways that subboards (quadrants) match). Thanks for the references to more general approaches. –  Geoffrey Irving Apr 16 '12 at 7:13
    
If you're curious, a routine for generating the lexicographically minimal element is here: github.com/girving/pentago/blob/… As with generation, the nasty part is what to do when different quadrants match after rotation. In this case it's easily solved with a small lookup table, and a similar approach should work for generation and coding as well. –  Geoffrey Irving Apr 16 '12 at 7:19

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.