使用Python进行Langford数字配对

Question

我尝试用Python生成Langford数。我已经写了下面的代码，它可以很好地获得第四个兰福德号码。这是我的代码：

import itertools

n=0
for l in set(itertools.permutations(["1", "1", "2", "2", "3", "3", "4", "4"])):
    t1, t2, t3, t4 = [i for i, j in enumerate(l) if j == "1"], [i for i, j in enumerate(l) if j == "2"], [i for i, j in enumerate(l) if j == "3"], [i for i, j in enumerate(l) if j == "4"]
    if abs(t1[1]-t1[0]) == 2 and abs(t2[1]-t2[0]) == 3 and abs(t3[1]-t3[0]) == 4 and abs(t4[1]-t4[0]) == 5:
        print("".join(l))
        n+=1
    else:
    pass

print(n)

我有两个问题：

• 首先，有没有技术可以让这段代码更快（目前它的结果是0.1s）
• 第二，你能给我一些提示，告诉我如何修改代码来获得第n个兰福德号码吗

我想知道，here是Langford数字的维基百科页面。在

如果你能抽出时间回答我，非常感谢！在

Answer 1

你让事情复杂化了：所需要的就是生成所有的排列，并消除那些不是Langford序列的排列。在

1-不要使用set(itertools...)，itertools已经返回了唯一的元素。
2-对于每个排列，您必须检查它是否是Langfort序列。
3-如果没有，断开并检查下一个
4-如果是，请检查它的反转尚未被整理，并将其保存在一组唯一的元素中 5-返回生成的唯一langfort序列

此代码对于n=4很快，并且可以找到任意n的序列；但是，时间复杂度是指数级的；超过n=6，它将需要相当长的时间才能完成。在

import itertools

def langfort(n):
    seq = [_ for _ in range(1, n+1)] * 2
    lang = set()
    for s in itertools.permutations(seq):
        for elt in seq:
            first = s.index(elt)
            if s[first+1:].index(elt) == elt:
                continue
            else:
                break
        else:
            if s[::-1] not in lang:
                lang.add(s)
    return lang

langfort(4)

输出：

^{pr2}$

性能：

在2011年mac book air上：

%timeit langfort(4)
10 loops, best of 3: 53.4 ms per loop

更多输出：

langfort(5)
set()          # there are no langfort(5) sequences

---

langfort(6)
set()          # there are no langfort(6) sequences

Answer 2

是的，有几种更快的方法来制作朗福德序列。在

首先，有一个简单的方法。我们不需要测试包含1到n的数字对的所有置换，而是生成从1到n的数字的置换，然后通过将每对数字放入下一个可用的槽位来尝试从这些置换中构建Langford序列。如果没有一对插槽可用，我们放弃这个排列，进入下一个。在

构建一个序列比简单地测试2n个项目的完全置换是否有效要慢一些，但这意味着当n较大时，我们需要测试一个批更少的置换。例如，如果n=7，就有7！=5040个排列，但是如果我们测试7对的排列，那就是14！=87178291200排列！在

不过，我们可以减少这个数字，因为它包含很多重复项。对于7对，唯一置换的数量是14! / (2**7)=681080400，因为交换7对中任何一对中的2个项目会产生重复的置换。不幸的是，itertools.permutations不关心重复，但是my answer here有一个不产生重复置换的置换生成器的代码。但是，6.81亿个排列仍然是一个很大的数字，而且需要很长的时间来测试它们。所以我们最好能避免这样做。在

import sys
from itertools import permutations

def place(t):
    slen = 2 * len(t)
    seq = [0] * slen
    for u in t:
        # Find next vacant slot
        for i, v in enumerate(seq):
            if v == 0:
                break
        else:
            # No vacant slots
            return
        j = i + u + 1
        if j >= slen or seq[j]:
            return
        seq[i] = seq[j] = u
    return tuple(seq)

def langford(n):
    count = 0
    for t in permutations(range(1, n+1)):
        seq = place(t)
        #if seq and seq < seq[::-1]:
        if seq:
            count += 1
            print(seq, count)
    return count // 2

def main():
    n = int(sys.argv[1]) if len(sys.argv) > 1 else 4
    count = langford(n)
    print(count)

if __name__ == '__main__':
    main()

n=7的输出

^{pr2}$

在我的旧2GHz机器上需要0.2秒。在

传统上，如果一个序列是另一个序列的反转，则认为2个Langford序列是相同的。处理这一问题的一种方法是将序列与其反向版本进行比较，并且仅当序列小于反向版本时才打印序列。你可以通过注释掉上面的代码来实现这一点

if seq:

在langford函数中取消对以下行的注释：

#if seq and seq < seq[::-1]:

---

上面的代码是一个改进，但是我们可以做得更好。我的下一个解决方案使用一种称为递归backtracking的技术。通过使用递归生成器函数，可以在Python中优雅地实现此技术。在

我们从一系列的零开始。从最高的数字开始，我们尝试在每个合法的插槽中放置一对数字，如果成功，我们递归放置下一对数字，如果没有剩余的数字，我们就找到了一个解决方案，我们可以得到它。在

import sys

def langford(n, seq):
    ''' Generate Langford sequences by recursive backtracking '''
    # The next n
    n1 = n - 1
    # Test each valid pair of positions for this n
    for i in range(0, len(seq) - n - 1):
        j = i + n + 1
        if not (seq[i] or seq[j]):
            # Insert this n into the sequence
            seq[i] = seq[j] = n
            if n1:
                # Recurse to add the next n
                yield from langford(n1, seq)
            else:
                # Nothing left to insert
                yield seq
            # Remove this n from the sequence in preparation
            # for trying the next position
            seq[i] = seq[j] = 0

def main():
    n = int(sys.argv[1]) if len(sys.argv) > 1 else 4
    for i, t in enumerate(langford(n, [0] * 2 * n), 1):
        print(t, i)
        if i % 1000 == 0:
            print(' ', i, end='\r', flush=True)
    print('\n', i // 2)

if __name__ == '__main__':
    main()

当if i % 1000 == 0:很大时，if i % 1000 == 0:可以让您看到进度。如果您注释掉print(t, i)行，这很方便。在

在我的机器上，这个代码可以在25秒内生成n=11的35584=2*17792序列。在

---

如果要将langford生成的序列收集到一个列表中，而不仅仅是打印它们，可以这样做：

n = 7
results = list(langford(n, [0] * 2 * n))

但是，如果您想这样做，必须对langford函数做一点小小的更改。上面写着

yield seq

把它改成

yield seq[:]

因此它生成seq的副本，而不是原始的seq列表。在

如果只想获取序列的计数（不计算反转），可以执行以下操作：

n = 7
count = sum(1 for _ in langford(n, [0] * 2 * n)) // 2
print(count)

使用yield seq可以正常工作。在

---

上面的代码对于n的较大值将很慢。Langford的数列计算方法很简单，但是没有一种计算方法是比较先进的。OEIS在A014552处有一个Langford序列号的列表。在