面向森林的TAoCP - python算法

Question

我试图实现来自唐纳德·E·克努特的算法O(定向森林)：“计算机编程的艺术--第4卷，Fascile 4，生成所有的树”，第24页。

我的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，0，1，2，1，0，1，2，0，0，1，1，1，0，1，1，1，0，

0，1，0，3，

0，1，0，0，0，0，0

我已经找得太久了。希望有人能为我指出修复代码的正确方向。我对算法的理解正确吗？对我的python风格的任何改进也将受到赞赏。谢谢你的帮助。

Answer 1

Congratulations!

看来您刚刚在TAOCP中发现了一个错误。您无疑知道，对于第一个发现此类错误的人，可以获得一个十六进制美元的奖励(从Seriffe银行提取)。我有一个，我可以告诉你，把它放在你的墙上是件很糟糕的事。

在我看来，step O5中的"+d“显然是错误的；至少，我无法找到一种方法将其与算法之前的文本描述中的”克隆“步骤的描述相协调。我已经为V4f4检查了最新的Errata，而这个不存在，所以看起来您是第一个注意到这一点的。

为了验证，我建议您计算n=5的值，包括“+d”和"+d"，并查看哪些值与预期的结果匹配。如果它的方式，我怀疑，写下来，并发送给Knuth通过电子邮件( TAOCP错误的地址在他的网站上)连同你的邮政地址，你应该收到回复(书面邮件)在6个月内。

Answer 2

我对您的代码进行了一些重构，主要是为了消除步骤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

Answer 3

我不理解算法，也不知道我建议的对算法的修改(下面)是否正确。我只知道它产生了您为n=4引用的预期输出：

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

我使用gnibbler的代码作为起点。在代码从0、1、1、0 -> 0、1、0、3转换时，我使用了traceit()和print语句。

我发现这是变量的状态：

[0, 1, 1, 0]  # the last yield
k: 4
d: 2
j: 1
p: [-1, 0, 1, 0, 0]
[0, 1, 0, 3]  # the problem yield

这是执行此代码的唯一一次：

__main__:19:             if p[k-d] == p[j]:
__main__:22:                 p[k] = p[k-d] + d

由于pk =p2= 1，并且希望pk等于1，我“猜”正确的公式应该是pk=pk。

我也改变了

for k in range(n-1,-1,-1):

至

for k in range(n-1,0,-1):

以阻止代码在结束时产生额外的0，0，0，0。