我写了一个程序，可以计算可能的兰福德序列数(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]开始作为Root
在每个深度处，我们获得所有可能发生的排列，其中所有出现的当前编号(= n深度)
分别是n深度的优秀位置。
在深度1中，我们得到4的所有可能位置=>
10000100
01000010
00100001
根据可能的排列，我检查是否存在冲突(如果所使用的位置之一已被另一个数字使用)。我通过计数为1的位数并将其与父位数进行比较来做到这一点。如果(currentPos xor Parent).count()== Parent.count()+ s，那么就不会有碰撞，我可以深入一处。 (检查所有3个可能满足约束的排列)
如果所有位都等于一个[((currentPos xor Parent).count()== s * n])，则我们达到了可能的排列，其中每个Number都是每个Number彼此分开的值。
到目前为止，这是可行的，但是我得到的每个数字都比我应该得到的结果大一倍，因为我没有考虑对称性。 (对于L(s，n)我总是得到2 * L(s，n))
我想知道如何利用树的对称性获得正确的结果。
我最初的想法是只使用首先使用ceil(len(Permutation)/2)排列(下图为红色选择)。但这导致了所有更糟的结果。
我不确定我应该在这里发布什么让你们帮助我-但我希望有人可以给我提示或其他内容
Ty in advcanded
最佳答案
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。您可能无法达到目标。如Wikipedia页面所述: