3

ツリーを作成するために使用したい辞書があります。アイデアは、指定されたインデックスの値を取得し、それをリストに追加することです。この値をディクショナリの次の項目のインデックスとして使用すると、None が取得されるまでプロセスが繰り返されます

私の辞書

dict = {
         'A' : 'AF',
         'BF': 'B',
         'AF': 'Z',
         'Z' : None,
         'B' : 'B'
       }

辞書をループして最初の値を取得できますが、辞書を再帰的にループするより良い方法はありません。

注 x は、指定したいインデックス パラメータです。つまり、A、BF、AF、Z、または B

def tree(x,dict):
   result = []
   for value in dict:
      result.append(value)
    #stuck somewhere here. 
    #I would like to use this value as an index again and pick next value. 
    #Do this until I have no further relation

   #print final results in a list
   print result

tree(x,dict) が呼び出されたとき、x = 'A' とすると、期待される結果は次のようになります。

['A','AF','Z']

あなたの支援と貢献に感謝します。

4

3 に答える 3

3

非再帰バージョンははるかに高速ですが、見栄えの良いバージョンがあります

>>> def tree(D, x):
        if x is None: 
            return []
        else: 
            return [x] + tree(D, D[x])


>>> tree(D, 'A')
['A', 'AF', 'Z']

またはワンライナーとして：

def tree(D, x):
    return [] if x is None else [x] + tree(D, D[x])

これは毎回 2 つのリストを追加するため、2 次ランタイムになりますが、パフォーマンスが必要な場合は使用.appendするだけで、ループを使用する方がはるかに実用的です。

于 2013-03-23T12:54:49.533 に答える
0

再帰ジェネレーターを試すこともできます。

# This will loop "forever"
data = {                                                                        
  'A' : 'AF',                                                          
  'BF': 'B',                                                           
  'AF': 'Z',                                                           
  'Z' : None,                                                          
  'B' : 'B'                                                            
}                                                                      
                                                                                                                                                   
def tree(key):                                                                  
  value = data.get(key)                                                         
  yield key                                                                     
  if value is not None:                                                         
    for value in tree(value):                                                   
      yield value                                                               
                                                                            
for value in tree("A"):                                                         
  # Do something with the value

EDIT : 上記の提案されたアプローチは、サイクルの検出に失敗し、再帰の深さが最大になるまでループします。

以下の再帰的アプローチは、訪問したノードを追跡してサイクルを検出し、そうであれば終了します。サイクルを見つける方法の最もわかりやすい説明は、この回答からのものです。

data = {
  'A' : 'AF',
  'BF': 'B',
  'AF': 'Z',
  'Z' : None,
  'B' : 'B'
}

def visit_graph(graph, node, visited_nodes):
    print "\tcurrent node: ", node, "\tvisited nodes: ", visited_nodes
    # None means we have reached a node that doesn't have any children
    if node is None:
        return visited_nodes
    # The current node has already been seen, the graph has a cycle we must exit
    if node in visited_nodes:
        raise Exception("graph contains a cycle")
    # Add the current node to the list of visited node to avoid cycles
    visited_nodes.append(node)
    # Recursively call the method with the child node of the current node
    return visit_graph(graph, graph.get(node), visited_nodes)


# "A" does not generate any cycle
print visit_graph(data, "A", [])

# Starting at "B" or "BF" will generate cycles
try:
    print visit_graph(data, "B", [])
except Exception, e:
    print e

try:
    print visit_graph(data, "BF", [])
except Exception, e:
    print e
于 2013-03-23T13:40:59.470 に答える
0 
def tree(x,dict):
    old_value = x
    while True:
        value = dict.get(old_value)
        if not value:
            break
        result.append(value)
    print result
于 2013-03-23T12:50:59.577 に答える