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

Question

bounty到期在5天内。该问题的答案有资格获得+ 100声望赏金。Barney Stinson希望引起更多关注对此问题：

我想知道我可以删除哪些排列以利用树的对称性，以便我可以为任何n计算L（2，n）

我写了一个程序，可以计算可能的兰福德序列数（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））

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

源代码：https://gist.github.com/masterholdy/0c257ee7d269e2db76dfd3149c38323a

---

[我最初的想法是只使用ceil（len（Permutation）/ 2）Permutations（下图为红色选择）。但这会导致所有较差的结果。

---

我不太确定我应该在这里发布什么让你们帮助我-但我希望有人能给我提示或其他内容

Ty in advcanded

---

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上的一半排列。

希望我能为您提供帮助。