<p>是的,有几种更快的方法来制作朗福德序列。在</p>
<p>首先,有一个简单的方法。我们不需要测试包含1到n的数字对的所有置换,而是生成从1到n的数字的置换,然后通过将每对数字放入下一个可用的槽位来尝试从这些置换中构建Langford序列。如果没有一对插槽可用,我们放弃这个排列,进入下一个。在</p>
<p>构建一个序列比简单地测试2n个项目的完全置换是否有效要慢一些,但这意味着当n较大时,我们需要测试一个<em>批</em>更少的置换。例如,如果n=7,就有7!=5040个排列,但是如果我们测试7对的排列,那就是14!=87178291200排列!在</p>
<p>不过,我们可以减少这个数字,因为它包含很多重复项。对于7对,唯一置换的数量是<code>14! / (2**7)</code>=681080400,因为交换7对中任何一对中的2个项目会产生重复的置换。不幸的是,<code>itertools.permutations</code>不关心重复,但是<a href="https://stackoverflow.com/a/43014919/4014959">my answer here</a>有一个不产生重复置换的置换生成器的代码。但是,6.81亿个排列仍然是一个很大的数字,而且需要很长的时间来测试它们。所以我们最好能避免这样做。在</p>
<pre><code>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()
</code></pre>
<p><strong>n=7的输出</strong></p>
^{pr2}$
<p>在我的旧2GHz机器上需要0.2秒。在</p>
<p>传统上,如果一个序列是另一个序列的反转,则认为2个Langford序列是相同的。处理这一问题的一种方法是将序列与其反向版本进行比较,并且仅当序列小于反向版本时才打印序列。你可以通过注释掉上面的代码来实现这一点</p>
<pre><code>if seq:
</code></pre>
<p>在<code>langford</code>函数中取消对以下行的注释:</p>
<pre><code>#if seq and seq < seq[::-1]:
</code></pre>
<hr/>
<p>上面的代码是一个改进,但是我们可以做得更好。我的下一个解决方案使用一种称为递归<a href="https://en.wikipedia.org/wiki/Backtracking" rel="nofollow noreferrer">backtracking</a>的技术。通过使用递归生成器函数,可以在Python中优雅地实现此技术。在</p>
<p>我们从一系列的零开始。从最高的数字开始,我们尝试在每个合法的插槽中放置一对数字,如果成功,我们递归放置下一对数字,如果没有剩余的数字,我们就找到了一个解决方案,我们可以得到它。在</p>
<pre><code>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()
</code></pre>
<p>当<code>if i % 1000 == 0:</code>很大时,<code>if i % 1000 == 0:</code>可以让您看到进度。如果您注释掉<code>print(t, i)</code>行,这很方便。在</p>
<p>在我的机器上,这个代码可以在25秒内生成n=11的35584=2*17792序列。在</p>
<hr/>
<p>如果要将<code>langford</code>生成的序列收集到一个列表中,而不仅仅是打印它们,可以这样做:</p>
<pre><code>n = 7
results = list(langford(n, [0] * 2 * n))
</code></pre>
<p>但是,如果您想这样做,<strong>必须</strong>对<code>langford</code>函数做一点小小的更改。上面写着</p>
<pre><code>yield seq
</code></pre>
<p>把它改成</p>
<pre><code>yield seq[:]
</code></pre>
<p>因此它生成<code>seq</code>的副本,而不是原始的<code>seq</code>列表。在</p>
<p>如果只想获取序列的计数(不计算反转),可以执行以下操作:</p>
<pre><code>n = 7
count = sum(1 for _ in langford(n, [0] * 2 * n)) // 2
print(count)
</code></pre>
<p>使用<code>yield seq</code>可以正常工作。在</p>
<hr/>
<p>上面的代码对于<code>n</code>的较大值将很慢。Langford的数列计算方法很简单,但是没有一种计算方法是比较先进的。OEIS在<a href="https://oeis.org/A014552" rel="nofollow noreferrer">A014552</a>处有一个Langford序列号的列表。在</p>