I have a simple application of [Polya's enumeration theorem](http://en.wikipedia.org/wiki/Polya_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.



Using Polya's enumeration theorem for explicit generation of instances
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 (Springer 2006) by Kaski 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.


