Langford 序列 - 利用对称性/去除对称性
Bar*_*son 7 c++ algorithm graph-algorithm
我写了一个程序，可以计算可能的 Langford 序列的数量（https://en.wikipedia.org/wiki/Langford_pairing）。
TL;DR Langfordsequences 由 L(s,n) 定义，其中 s 是某个数量的出现次数
和 n 是可能的数字/颜色的数量，这些数字定义了它们彼此之间有多少个位置
图片将是 L(2, 4) ==> 每个数字有 2 次出现，并且有 4 个不同的数字。|L(2,4)|的数量 将是 1，因为只有一种可能的排列满足约束
计算可能排列数量背后的想法如下。L(2,4) 我们从一个全为 0 的 Bitset[s*n] 作为根
在每个深度，我们得到所有可能的排列，其中当前数字（= n 深度）的所有出现都是极好的 n 深度位置。
在深度 1 我们得到了所有可能的位置 4 =>
10000100
01000010
00100001
每个可能的排列我检查是否有冲突（如果使用的位置之一已被另一个数字使用）。我通过计算 1 的位数并将它们与父位进行比较来做到这一点。如果 (currentPos xor Parent).count() == Parent.count() + s 那么没有碰撞，我可以更深一层。（检查满足约束的 3 的所有可能排列）
如果所有位都等于 1 [(currentPos xor Parent).count() == s*n] 我们达到了一个可能的排列，其中每个数字是每个数字彼此分开的值。
到目前为止，这是有效的，但是与我应该得到的结果相比，我将每个数字都加倍了，因为我没有考虑对称性。（对于 L(s,n) 我总是得到 2*L(s,n)）
我想知道如何利用树的对称性来获得正确的结果。
我最初的想法是只使用首先使用 ceil(len(Permutation) / 2) Permutations（下图中的红色选择）。但这导致了更糟糕的结果。
我不太确定我应该在这里发布什么让你们帮助我 - 但我希望有人能给我一个提示或其他东西
高级
小智 2
L(s, n)是“直到顺序颠倒”，参见例如https://oeis.org/A014552。这意味着例如|L(2, 4)|我们有
4 1 3 1 2 4 3 2
和
2 3 4 2 1 3 1 4
都满足该性质，但其中一个正好与另一个相反，所以|L(2, 4)| = 1。
为了在您的算法中考虑到这一点，您可以在第一级检查左侧的空闲位多于右侧的空闲位。
注意：您的算法枚举了所有解决方案，因此复杂度为> L(2, n)且n = 20已经超过2^41。你可能达不到这一点。正如维基百科页面上提到的：
对于大量
n解，可以通过代数方法更有效地计算