2

我尝试实现Donald E. Knuth 的算法 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, 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 风格的任何改进也值得赞赏。谢谢你的帮助。

4

5 回答 5

2

恭喜！

看起来您似乎刚刚在 TAOCP 中发现了一个错误。正如您无疑知道的那样，第一个发现此类错误的人将获得 1 美元的奖励（取自 San Serife 银行）。我有一个，我可以告诉你，把它贴在你的墙上是一件很糟糕的事情。

在我看来，步骤O5中的“ +d ”肯定是错误的；至少，我找不到一种方法来将它与算法之前的文本描述中的“克隆”步骤的描述相协调。我检查了 V4f4 的最新勘误表，但其中没有，所以看起来您是第一个注意到这一点的人。

为了验证，我建议您计算带有和不带有“ +d ”的n=5的值，并查看与预期结果匹配的值。如果它按照我怀疑的方式进行，请将其写下来并通过电子邮件（TAOCP 错误的地址在他的网站上）连同您的邮政地址一起发送给 Knuth，您应该会在 6 个月内收到回复（通过纸质邮件） .

于 2009-11-11T10:40:40.163 回答
0

我挖掘了原始文章：SIAM​​ Journal of Computing，T. Beyer 和 SM 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 的算法不起作用。找出来会很酷。

于 2009-10-29T21:29:47.900 回答
0

我稍微重构了您的代码，主要是为了消除第 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
于 2009-10-27T23:18:42.893 回答
0

我不了解该算法，也不知道我对算法（如下）的建议更改是否正确。我所知道的是，它会产生您为 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

由于 p[kd]=p[2]=1，并且您希望 p[k] 等于 1，我“猜测”正确的公式应该是 p[k]=p[kd]。

我也变了

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

至

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

阻止代码在最后产生额外的 [0, 0, 0, 0]。

于 2009-10-28T02:41:25.713 回答
0

答案是：每个人都是对的！

Knuth 的算法计算父代码，而不是级别代码。似乎“唐纳德”仍在考虑父代码，即使在评论 B&H 算法使用级别代码时也是如此。

但是，如果您查看算法 O 的文本，您应该注意到 Knuth 提到“每个规范森林直接由其父指针序列 p 1 ...p n以节点的前序表示。”

因此，该算法应该使用父代码，而不是级别代码。那个 Knuth，他是个狡猾的人......所以，我公然复制了 unutbu 的代码，想出一个看起来更像你写的代码生成版本：

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]
         for q in range(1,k):
             if p[k-q] == p[j]: break
         while True:
             p[k] = p[k-q]
             if k==n:
                 break
             k+=1

 if __name__ == "__main__":
     for el in generate_oriented_forest(4):
         print el

希望这回答了你的问题。:)

于 2011-03-17T20:38:58.147 回答