在给定高度、宽度和每个元素的状态数的情况下找到唯一的、非等效配置的算法

Question

所以最近，我一直在尝试解决代码挑战，但找不到答案。问题不在于实现，而在于实现什么。可以在此处找到提示 http://pastebin.com/DxQssyKd

提示中的主要有用信息如下

“编写一个函数 answer(w, h, s)，它接受 3 个整数并返回可以在 w block 宽和 h block 高的星形网格上找到的唯一、非等效配置的数量，其中每个天体都有s 可能的状态。等效性定义如上:任何两个星格，每个天体都处于相同状态，其中行和列的实际顺序无关紧要(因此可以自由交换)。星格标准化意味着网格的宽度和高度总是在 1 到 12 之间，包括在内。虽然每个网格中有各种天体，但这些天体的状态数在 2 到 20 之间，包括在内。答案可以超过 20数字长，因此将其作为十进制字符串返回。”

等价的方式是

00
01 

相当于

01
00  

等等。问题是，我应该使用什么算法？我知道这在某种程度上与排列、组合和群论有关，但我找不到任何具体内容。

Answer 1

关键武器是Burnside's lemma , 等于对称群 G = S_w × S_h 作用于组态 X = ([w] × [h] → [ s]) (即答案)到总和 1/|G| ∑_g∈G |X^g|，其中 X^g = {x | g.x = x}是由g固定的元素集合。

给定 g，计算 |X^g| 很简单:使用 g 在顶点 [w] × [h] 上构造一个图，其中 (i, j) 和 g 之间有一条边(i, j) 对于所有 (i, j)。计算 c，连接组件的数量，并返回 s^c。原因是连通分量中的每个顶点都必须具有相同的状态，但不同分量中的顶点是不相关的。

现在，对于 12 × 12 的网格，g 的值太多了，无法对其进行计算。幸运的是，当 g 和 g' 共轭时(即存在一些 h 使得 h.g.h^-1 = g')，我们发现 |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|。因此，我们可以对共轭类求和，并将每一项乘以类中群元素的数量。

最后一 block 是G = S_w × S_h的共轭类结构。这个直积的共轭类结构实际上就是 S_w 和 S_h 的共轭类的直积。 S_n 的共轭类与 integer partitions 一一对应的 n，可通过标准递归方法枚举。要计算类(class)的规模，您需要除以 n!通过分区项的乘积(因为循环的循环排列是等效的)以及相同大小的循环之间的对称数的乘积(多重性的阶乘的乘积)。参见 https://groupprops.subwiki.org/wiki/Conjugacy_class_size_formula_in_symmetric_group .