Langford 序列 - 利用对称性/移除对称性
Langford Sequence - Utilize symmetry / Remove symmetry
我写了一个程序，可以计算可能的 Langford 序列数 (https://en.wikipedia.org/wiki/Langford_pairing)。
TL;DR Langfordsequences 由 L(s,n) 定义，其中 s 是某个数字出现的次数
n 是可能的数量 numbers/colors
这些数字定义了它们必须彼此相距多少个位置
图片为 L(2, 4) ==> 每个数字出现 2 次，共有 4 个不同的数字。
|L(2,4)| 的数量将是 1，因为只有一种可能的排列满足约束
计算可能排列数量的思路如下。大号(2,4)
我们从全 0 的 Bitset[s*n] 开始作为 Root
在每个深度，我们得到所有可能的排列，其中当前编号的所有出现（= n 深度）
是优秀的 n 深度位置。
在深度 1 中，我们得到 4 的所有可能位置 =>
10000100
01000010
00100001
Per Possible Permutation 我检查是否存在冲突（如果使用的位置之一已被另一个号码使用）。我通过计算为 1 的位数并将它们与父位进行比较来做到这一点。 if (currentPos xor Parent).count() == Parent.count() + s 那么没有碰撞，我可以更深入一点。 （检查满足约束条件的 3 的所有可能排列）
如果所有位都等于 1 [(currentPos xor Parent).count() == s*n] 我们得到了一个可能的排列，其中每个数字都是其彼此相距的值。
到目前为止这是有效的，但我得到的每个数字都比我应该得到的结果翻了一番，因为我没有考虑对称性。 （对于 L(s,n)，我总是得到 2*L(s,n)）
我想知道如何利用树的对称性来获得正确的结果。
我最初的想法是只使用 first to ceil(len(Permutation) / 2) Permutations（下图中的红色选择）。但这导致了每一个更糟糕的结果。
我不太确定我应该在这里张贴什么让你们帮助我 - 但我希望有人能给我提示或其他东西
Ty 进阶
L(s, n) 是 "up to reversal of the order" 参见例如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。你可能达不到这个。如维基百科页面所述：
for large n the number of solutions can be calculated more efficiently by algebraic methods
只要 N 为奇数，您就可以删除 level/depth 1 上的一半排列。如果 N 是偶数，删除 level/depth 2.
上的一半排列
希望能帮到你
我写了一个程序，可以计算可能的 Langford 序列数 (https://en.wikipedia.org/wiki/Langford_pairing)。
TL;DR Langfordsequences 由 L(s,n) 定义，其中 s 是某个数字出现的次数
n 是可能的数量 numbers/colors 这些数字定义了它们必须彼此相距多少个位置
图片为 L(2, 4) ==> 每个数字出现 2 次，共有 4 个不同的数字。 |L(2,4)| 的数量将是 1，因为只有一种可能的排列满足约束
计算可能排列数量的思路如下。大号(2,4) 我们从全 0 的 Bitset[s*n] 开始作为 Root
在每个深度，我们得到所有可能的排列，其中当前编号的所有出现（= n 深度） 是优秀的 n 深度位置。
在深度 1 中，我们得到 4 的所有可能位置 =>
10000100
01000010
00100001
Per Possible Permutation 我检查是否存在冲突（如果使用的位置之一已被另一个号码使用）。我通过计算为 1 的位数并将它们与父位进行比较来做到这一点。 if (currentPos xor Parent).count() == Parent.count() + s 那么没有碰撞，我可以更深入一点。 （检查满足约束条件的 3 的所有可能排列）
如果所有位都等于 1 [(currentPos xor Parent).count() == s*n] 我们得到了一个可能的排列，其中每个数字都是其彼此相距的值。
到目前为止这是有效的，但我得到的每个数字都比我应该得到的结果翻了一番，因为我没有考虑对称性。 （对于 L(s,n)，我总是得到 2*L(s,n)）
我想知道如何利用树的对称性来获得正确的结果。
我最初的想法是只使用 first to ceil(len(Permutation) / 2) Permutations（下图中的红色选择）。但这导致了每一个更糟糕的结果。
我不太确定我应该在这里张贴什么让你们帮助我 - 但我希望有人能给我提示或其他东西
Ty 进阶
L(s, n) 是 "up to reversal of the order" 参见例如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。你可能达不到这个。如维基百科页面所述：
for large
nthe number of solutions can be calculated more efficiently by algebraic methods
只要 N 为奇数，您就可以删除 level/depth 1 上的一半排列。如果 N 是偶数，删除 level/depth 2.
上的一半排列希望能帮到你