algorithm to find unique, non equivalent configurations given the height, the width, and the number of states each element can be

Question

SO recently, I have been attempting to solve a code challenge and can not find the answer. The issue is not the implementation, but rather what to implement. The prompt can be found here http://pastebin.com/DxQssyKd

the main useful information from the prompt is as follows

"Write a function answer(w, h, s) that takes 3 integers and returns the number of unique, non-equivalent configurations that can be found on a star grid w blocks wide and h blocks tall where each celestial body has s possible states. Equivalency is defined as above: any two star grids with each celestial body in the same state where the actual order of the rows and columns do not matter (and can thus be freely swapped around). Star grid standardization means that the width and height of the grid will always be between 1 and 12, inclusive. And while there are a variety of celestial bodies in each grid, the number of states of those bodies is between 2 and 20, inclusive. The answer can be over 20 digits long, so return it as a decimal string."

The equivalency is in a way that

00
01 

is equivalent to

01
00  

and so on. The problem is, what algorithm(s) should I use? i know this is somewhat related to permutations, combinations, and group theory, but I can not find anything specific.

Answer 1

The key weapon is Burnside's lemma, which equates the number of orbits of the symmetry group G = S_w × S_h acting on the set of configurations X = ([w] × [h] → [s]) (i.e., the answer) to the sum 1/|G| ∑_g∈G |X^g|, where X^g = {x | g.x = x} is the set of elements fixed by g.

Given g, it's straightforward to compute |X^g|: use g to construct a graph on vertices [w] × [h] where there is an edge between (i, j) and g(i, j) for all (i, j). Count c, the number of connected components, and return s^c. The reasoning is that every vertex in a connected component must have the same state, but vertices in different components are unrelated.

Now, for 12 × 12 grids, there are far too many values of g to do this calculation on. Fortunately, when g and g' are conjugate (i.e., there exists some h such that h.g.h^-1 = g') we find that |X^g'| = |{x | g'.x = x}| = |{x | h.g.h^-1.x = x}| = |{x | g.h^-1.x = h^-1.x}| = |{h.y | g.y = y}| = |{y | g.y = y}| = |X^g|. We can thus sum over conjugacy classes and multiply each term by the number of group elements in the class.

The last piece is the conjugacy class structure of G = S_w × S_h. The conjugacy class structure of this direct product is really just the direct product of the conjugacy classes of S_w and S_h. The conjugacy classes of S_n are in one-to-one correspondence with integer partitions of n, enumerable by standard recursive methods. To compute the size of the class, you'll divide n! by the product of the partition terms (because circular permutations of the cycles are equivalent) and also by the product of the number of symmetries between cycles of the same size (product of the factorials of the multiplicities). See https://groupprops.subwiki.org/wiki/Conjugacy_class_size_formula_in_symmetric_group.