python中面向森林的TAoCP算法

Question

我试图实现donalde.Knuth的Algorithm O (Oriented forests)来自donalde.Knuth:“计算机编程的艺术-第4卷，第4分册，生成所有的树”。在

我的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]， [1,0,1]条， [0，1，1，0]

[0，1，0，3]

[0，1，0，0]， [0，0，0，0]。在

我已经在找虫子了。希望有人能给我指出修正代码的正确方向。我对算法的理解正确吗？我的python风格的任何改进也值得赞赏。谢谢你的帮助。在

Answer 1

我不了解算法，也不知道我对算法（下面）所建议的更改是否正确。我只知道它会产生你引用的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的代码作为起点。我使用了traceit()和print语句来跟踪代码从[0，1，1，0]-->；[0，1，0，3]转换的代码。在

我发现这是变量的状态：

^{pr2}$

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

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

既然p[k-d]=p[2]=1，而你希望p[k]等于1，我“猜想”正确的公式应该是 p[k]=p[k-d]。在

我也变了

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

到

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

以阻止代码在结尾产生额外的[0，0，0，0]。在

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

恭喜你！

看起来你刚刚在TAOCP中发现了一个错误。你肯定知道，第一个发现这种错误的人会得到一个十六进制美元的奖励（从圣塞里夫银行提取）。我有一个，我可以告诉你，把它挂在你的墙上是件很糟糕的事。在

在我看来，步骤O5中的“+d”是错误的；至少，我找不到一种方法来与算法之前的文本描述中的“克隆”步骤的描述相一致。我已经检查了V4f4的最新勘误表，但这个不在那里，所以看起来你是第一个注意到这一点的人。在

为了验证，我建议您计算带有和不带“+d”的n=5的值，并查看哪些与预期结果相匹配。如果它是我怀疑的，把它写下来，连同你的邮政地址一起通过电子邮件发送给Knuth（TAOCP bug的地址在他的网站上），你应该在6个月内收到回复（通过纸质邮件）。在