3

データ:依存関係リスト。非周期的であることがすでに確認されています。したがって、ここでは、「a」は「b」、「c」(cはdに依存)などに依存します。

A = { 'a' :  dict(b=1, c=1),
    'c' : dict(d=1),
    'd' : dict(e=1,f=1,g=1),
    'h' : dict(j=1)
    }

たとえば、「a」で始まるチェーンを見つけるためのトップダウンの再帰的なソリューションが必要です:a、c、d、e、g、f、b

したがって、現在(非ジェネレータソリューション):

def get_all(D,k):
    L = []
    def get2(D,k):
        L.append(k)
        for ii in D.get(k,[]):
            get2(D, ii)
    get2(D,k)
    return L

明らかに、これはかなり弱いです:)私はそこで利回りを得る方法について頭を悩ませてきました、そして私はすべてのpy-fooy'allがこれにもたらすことができることを感謝します。

4

2 に答える 2

6

どちらの回答でも同じ結果が得られますが、私の質問の読みが正しければ、特定のグラフへの単純な変更に対して間違った回答が返されます。グラフの指示に従って) 出力は次のとおりです。 a c d e g f b d e g f

これはまったく役に立ちません。グラフのどのノードがすでに訪問されたかを追跡する、この小さなバリエーションを試してください。

def get_all(D, k, seen=None):
    if not seen:
        seen = set( )
    if k not in seen:
        seen.add(k)
        yield k
        for ii in D.get(k, []):
            for jj in get_all(D, ii, seen):
                yield jj
于 2008-09-20T17:43:51.217 に答える
4

これを試して:

#!/usr/bin/env python

def get_all(D, k):
    yield k
    for ii in D.get(k, []):
        for jj in get_all(D, ii):
            yield jj

A = { 'a' : dict(b=1, c=1),
    'c' : dict(d=1),
    'd' : dict(e=1,f=1,g=1),
    'h' : dict(j=1)
    }

for ii in get_all(A,'a'):
    print ii

私にくれ

steve @ rei:〜/ code / tmp
$ python recur.py
a
c
d
e
g
f
b
于 2008-09-20T16:18:00.657 に答える