向森林TAOCP - 算法在python

Question

我嘗試從唐納德·E·Knuth的實施Algorithm O (Oriented forests)：「計算機程序設計藝術 - 第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風格的任何改進也表示讚賞。謝謝你的幫助。

Answer 1

我重構你的代碼一點點，主要是爲了消除在步驟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 2

我不明白的算法，而且不知道如果我對算法的建議更改（如下）是正確的。我所知道的是，它會產生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()和打印語句來跟隨從[0,1,1,0] - > [0,1,0,3]過渡的代碼。

我發現的是，這是變量的狀態：

[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]停止的代碼。

Answer 3

我挖掘了最初的關聯：SIAM​​ Journal of Computing，T. Beyer and 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的算法不起作用。會發現很酷。

Answer 4

恭喜！

它確定看起來像只是在TAOCP中發現錯誤。你毫無疑問知道，這種錯誤的第一個發現者有一個十六進制美元（在聖塞裏夫銀行繪製）的獎勵。我有一個，我可以告訴你，這是一個地獄的事情，把你的牆上。

在我看來，步驟O5中的「+ d」是錯誤的;至少，我找不到一種方法將其與算法之前的文本描述中的「克隆」步驟的描述進行協調。我已經檢查了最新的V4f4勘誤表，而這個不在那裏，所以看起來你是第一個注意到這一點的人。

爲了驗證，我建議你既沒有了「+ d」計算值N = 5，看看哪些符合預期的結果。如果按照我懷疑的方式進行，寫下來並通過電子郵件將其發送給Knuth（TAOCP錯誤的地址在他的網站上）以及您的郵寄地址，並且您應在6個月內收到回覆（通過紙質郵件） 。

Answer 5

答案是：大家都對！

Knuth的算法計算父代碼，而不是等級代碼。看起來「唐納德」仍然在考慮母代碼，即使同時指出B算法使用代碼代替。

但是，如果你看一下算法的O的文字，你應該注意到克努特提到，「每個規範森林是由其父指針P 的序列直接表示。P ñ在序節點「。

所以，這個算法應該使用父代碼，而不是級別代碼。 那克努特，他是一個狡猾的一個... 所以，我大膽地抄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 

希望，這回答了你題。 :)