面向森林的 TAoCP - Python 中的算法
我正在尝试实现一本书中的算法，书名是《计算机程序设计艺术》第四卷，作者是Donald E. Knuth，具体是第24页的“算法O（有向森林）”。
我用Python写的代码如下：
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]]
else:
k_largest = 0
for k in range(1,n):
if p[k] != 0: k_largest = k
k = k_largest
if k == 0: return
j = p[k]
d = k-j
if p[k-d] == p[j]: p[k] = p[j]
else: p[k] = p[k-d] + d
while k != n:
#print k, p
k = k+1
if p[k-d] == p[j]: p[k] = p[j]
else: p[k] = p[k-d] + d
if __name__ == "__main__":
for el in generate_oriented_forest(4):
print el
# According to page 23 and also Table 1 p.4 I would expect the sequence:
# 0123, 0122, 0121, 0120, 0111, 0110, 0101, 0100, 0000
我的实现结果是：
[0, 1, 2, 3],
[0, 1, 2, 2],
[0, 1, 2, 1],
[0, 1, 2, 0],
[0, 1, 1, 1],
[0, 1, 1, 0],
[0, 1, 0, 3],
[0, 1, 0, 0],
[0, 0, 0, 0]。
我已经花了很长时间在找错误。希望有人能帮我指点一下，告诉我怎么修正我的代码。我的算法理解是否正确？如果能给我一些关于Python代码风格的改进建议，我也非常感激。谢谢大家的帮助。
5 个回答
我对你的代码做了一些小改动，主要是为了去掉第5步中的重复部分。
不过输出的结果还是和你得到的一样。
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] + d
if k==n:
break
k+=1
if __name__ == "__main__":
for el in generate_oriented_forest(4):
print el
我找到了原始的文章：SIAM计算杂志，T. Beyer和S.M. Hedetniemi的《常数时间生成有根树》。这篇论文对算法的解释非常清楚。下面是我的实现：
def generate_oriented_forest_2(n):
"""SIAM J. COMPUT. Vol. 9, No. 4, November 1980
T. Beyer and S.M. Hedetniemi: constant time generation of rooted trees."""
L = range(-1, n)
while True:
yield L[1:]
if L[n] > 0: L[n] = L[L[n]]
else:
for p in range(n-1, 0, -1):
if L[p] != 0: break
else: break
for q in range(p-1, 0, -1):
if L[q] == L[p] - 1: break
i = p
while i <= n:
L[i] = L[i-(p-q)]
i += 1
这个实现给了我预期的结果。不过我还是在想，为什么Knuth的算法不管用。能搞清楚这个问题就太好了。
恭喜你！
看起来你刚刚发现了《计算机程序设计艺术》中的一个错误。正如你所知道的，发现这种错误的人可以获得一个十六进制美元的奖励（由圣塞里夫银行支付）。我也有过一次这样的经历，真的很值得挂在墙上炫耀。
我觉得在步骤O5中的“+d”是错的；至少，我找不到任何方法能把它和算法前面描述的“克隆”步骤对上。我查了最新的V4f4勘误表，这个错误没有在里面，所以看起来你是第一个注意到这个问题的人。
为了验证这个错误，我建议你计算一下当n=5时，有和没有“+d”的结果，看看哪个结果符合预期。如果结果和我猜的一样，那就把你的发现写下来，发邮件给Knuth（关于《计算机程序设计艺术》错误的邮箱地址在他的网站上可以找到），并附上你的邮寄地址，你应该会在6个月内收到他的回复（通过纸质邮件）。