<p>我不了解算法,也不知道我对算法(下面)所建议的更改是否正确。我只知道它会产生你引用的n=4的预期输出:</p>
<pre><code>def generate_oriented_forest(n):
"""Algorithm O from Knuth TAoCP, Fascicle 4, p. 25. """
p = range(-1,n)
while True:
yield p[1:]
if p[n] > 0:
p[n] = p[p[n]]
continue
for k in range(n-1,0,-1):
if p[k] != 0: break
else:
break
j = p[k]
d = k-j
while True:
if p[k-d] == p[j]:
p[k] = p[j]
else:
p[k] = p[k-d]
if k==n:
break
k+=1
</code></pre>
<p>我用gnibbler的代码作为起点。我使用了<a href="http://www.dalkescientific.com/writings/diary/archive/2005/04/20/tracing_python_code.html" rel="nofollow noreferrer">traceit()</a>和print语句来跟踪代码从[0,1,1,0]-->;[0,1,0,3]转换的代码。在</p>
<p>我发现这是变量的状态:</p>
^{pr2}$
<p>这是唯一一次执行此代码:</p>
<pre><code>__main__:19: if p[k-d] == p[j]:
__main__:22: p[k] = p[k-d] + d
</code></pre>
<p>既然p[k-d]=p[2]=1,而你希望p[k]等于1,我“猜想”正确的公式应该是
p[k]=p[k-d]。在</p>
<p>我也变了</p>
<pre><code>for k in range(n-1,-1,-1):
</code></pre>
<p>到</p>
<pre><code>for k in range(n-1,0,-1):
</code></pre>
<p>以阻止代码在结尾产生额外的[0,0,0,0]。在</p>