擅长:python、mysql、java
<p>你让事情复杂化了:所需要的就是生成所有的排列,并消除那些不是Langford序列的排列。在</p>
<p>1-不要使用<code>set(itertools...)</code>,itertools已经返回了唯一的元素。<br/>
2-对于每个排列,您必须检查它是否是Langfort序列。<br/>
3-如果没有,断开并检查下一个<br/>
4-如果是,请检查它的反转尚未被整理,并将其保存在一组唯一的元素中
5-返回生成的唯一langfort序列</p>
<p>此代码对于n=4很快,并且可以找到任意<code>n</code>的序列;但是,时间复杂度是指数级的;超过<code>n=6</code>,它将需要相当长的时间才能完成。在</p>
<pre><code>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)
</code></pre>
<h3>输出:</h3>
^{pr2}$
<h3>性能:</h3>
<p>在2011年mac book air上:</p>
<pre><code>%timeit langfort(4)
10 loops, best of 3: 53.4 ms per loop
</code></pre>
<h3>更多输出:</h3>
<pre><code>langfort(5)
set() # there are no langfort(5) sequences
</code></pre>
<hr/>
<pre><code>langfort(6)
set() # there are no langfort(6) sequences
</code></pre>