Langford序列-利用对称性/消除对称性

Question

我编写了一个程序，可以计算可能的兰福德序列(https://en.wikipedia.org/wiki/Langford_pairing)的数量。

Dlangford序列由L(s，n)定义，其中s是某个数的发生量。

N是可能的数字/颜色的数量，数字定义了它们必须相互连接的位置。

​

​

图为L(2，4) ==>，每个数有2个发生，有4个不同的数目。由于只有一种可能的排列满足这些约束，所以x(2，4)x的个数为1。

​

​

计算可能排列的数量的思想如下所示。L(2,4)我们以所有0的位集*n作为根开始

在每个深度，我们得到所有可能的排列，其中所有发生的卷曲数(= n-深度)是优秀的n-深度位置相隔。

在深度1中，我们得到了4 =>的所有可能位置。

10000100

01000010

00100001

根据可能的排列，我检查是否存在碰撞(如果所使用的位置之一已经被另一个数字所使用)。我通过计算1位的数量并将其与父位进行比较来做到这一点。如果(currentPos xor父).count() == Parent.count() +s，那么就没有碰撞，我可以深入到一个深度。(检查所有可能的排列，为3统计约束)

如果所有位都等于一个(currentPos，xor父).count() == s*n，则可能发生排列，其中每个数都是每个数的值。

​

​

这是目前为止的工作，但我得到的每一个数字比我应该得到的结果加倍，因为我没有考虑到对称性。(对于L(s，n)，我总是得到2*L(s，n))

我想知道如何利用树的对称性来得到正确的结果。

我最初的想法是只使用“先用”(len(置换)/ 2)排列(红色-在下面的图像上选择)。但这导致了每一个更糟糕的结果。

​

​

我不太确定在这里我该怎么做才能让你们帮我--但我希望有人能给我个提示或什么的

Ty在前进

Answer 1

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，用代数方法

可以更有效地计算解的个数。

Answer 2

一旦N是奇数，就可以删除级别/深度1上的排列的一半。如果N为偶数，则删除级别/深度2上的排列的一半。

我希望我能帮你。