2

私は、Donald E. Knuth のAlgorithm O (Oriented forests)を実装しようとしています: 'The Art of Computer Programming - Volume 4, Facile 4, Generating All Trees' on page 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 でエラーが見つかったようです。ご存じのとおり、このようなエラーを最初に見つけた人には、16 進数で 1 ドル (サン セリフ銀行から引き出されます) の報酬があります。私はそれを持っています、そして私はあなたに言うことができます、あなたの壁に置くのは地獄です.

確かに、ステップO5の " +d "が間違っているように思えます。少なくとも、アルゴリズムの前のテキスト説明の「複製」ステップの説明と一致させる方法を見つけることができません。V4f4 の最新の正誤表を確認しましたが、これはそこにありません。最初にこれに気付いたのはあなたのようです。

確認するには、「 +d 」を使用した場合と使用しない場合の両方でn=5の値を計算し、どれが期待される結果と一致するかを確認することをお勧めします。私が思うように進んだ場合は、それを書き留めて電子メールで Knuth (TAOCP バグのアドレスは彼の Web サイトにあります) とあなたの住所を添えて送ってください。 .

于 2009-11-11T10:40:40.163 に答える
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

答えは：誰もが正しいです！

Knuth のアルゴリズムは、レベル コードではなく、親コードを計算します。「THE ドナルド」は、B & H アルゴリズムが代わりにレベル コードを使用していることに言及しながらも、まだ親コードの観点から考えていたようです。

ただし、Algorithm O のテキストを見ると、Knuth が「各正規の森は、ノードの前の順序で親ポインター p 1 ...p nのシーケンスによって直接表現される」と述べていることに気付くはずです。

したがって、このアルゴリズムは、レベル コードではなく、親コードを使用することになっています。そのクヌース、彼は狡猾な人です...だから、私は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 に答える
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

私は元の論文を掘り起こしました: SIAM Journal of Computing, T. Beyer and SM Hedetniemi, 'Constant Time Generation of rooted trees". この論文はアルゴリズムを非常によく説明しています. これが私の実装です:

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

それは私に期待される結果を与えます。しかし、なぜクヌースのアルゴリズムが機能しないのか、私はまだ疑問に思っています。見つけるのはクールだろう。

于 2009-10-29T21:29:47.900 に答える