再帰を使用して大きなdictからサブディックを作成する

Question

私は、親子の崩壊連鎖の中のさまざまな種をリンクする辞書を持っています。例えば、この辞書に

d = { 
    'A':{'daughter':['B']}, 
    'B':{'daughter':['C']}, 
    'C':{'daughter':['D']}, 
    'D':{'daughter':['None']}, 
    'E':{'daughter':['F']}, 
    'F':{'daughter':['G']}, 
    'G':{'daughter':['H']}, 
    'H':{'daughter':[None]} 
} 

、トップレベルの鍵は、「親」と「子」である（すなわち、どの親が鎖中に減衰する）キーのように定義される：辞書内の値のアイテム親キーに添付されます。娘のためにNoneが与えられるとき、それは鎖の終わりであると考えられます。

私は、開始親のユーザの入力に従ってチェーン内の項目を含むサブ辞書を返す関数を必要とします。また、チェーン内の各アイテムの位置を知りたいと思います。サブディクショナリでは、これは第2フィールド（'position'）になります。例えば

ユーザーが「A」でチェーンを開始したい場合、私は返すように機能したいと思います：

同様

{'A':{'position':1, 'daughter':['B']}, 
'B':{'position':2, 'daughter':['C']}, 
'C':{'position':3, 'daughter':['D']}, 
'D':{'position':4, 'daughter':['None']}} 

、開始値が「E」だった場合、私はそれを希望戻る：

{'F':{'position':1, 'daughter':['G']}, 
'G':{'position':3, 'daughter':['H']}, 
'H':{'position':4, 'daughter':['None']}} 

をリンクは一対一すなわち、1つの項目が別のものに崩壊するときにこれが比較的容易であり、別など

に私は今、以下のように、より複雑な例を使用する場合は、あなたを見ることができる「B」は実際には「C」と「D」の両方に崩壊し、そこからチェーンは分離しています。

A => B => C => E => G及びA => B => D => F => Hこの場合

d = { 
    'A':{'daughter':['B']}, 
    'B':{'daughter':['C', 'D']}, 
    'C':{'daughter':['E']}, 
    'D':{'daughter':['F']}, 
    'E':{'daughter':['G']}, 
    'F':{'daughter':['H']}, 
    'G':{'daughter':[None]}, 
    'H':{'daughter':[None]} 
} 

Iは、以下を返す関数を希望出力。あなたは、2つの鎖の転用のために気付くでしょう。位置の値はヒーラーのレベルに近く、例えば、 C = 3およびD = 4であるが、全く同じではない。私は、Cチェーンを一番下にしてDチェーンを繰り返すことは望ましくありません。

{'A':{'position':1, 'daughter':['B']}, 
'B':{'position':2, 'daughter':['C']}, 
'C':{'position':3, 'daughter':['E']}, 
'D':{'position':4, 'daughter':['F']} 
'E':{'position':5, 'daughter':['G']} 
'F':{'position':6, 'daughter':['H']} 
'G':{'position':8, 'daughter':['None']} 
'H':{'position':9, 'daughter':['None']} 
} 

この関数は、チェーン内の複数の流用に対処できなければなりません。

あなたがダウンCからすべての道を行くにしたくない場合は、breadth-first searchが役立つかもしれ

Answer 1

マーク。

def bfs(d, start): 
    answer = {} 
    queue = [start] 
    head = 0 

    while head < len(queue): 
     # Fetch the first element from queue 
     now = queue[head] 
     answer[now] = { 
      'position': head+1, 
      'daughter': d[now]['daughter'] 
     } 

     # Add daughters to the queue 
     for nxt in d[now]['daughter']: 
      if nxt == None: 
       continue 
      queue.append(nxt) 

     head += 1 

    return answer 

d = { 
    'A': {'daughter': ['B']}, 
    'B': {'daughter': ['C', 'D']}, 
    'C': {'daughter': ['E']}, 
    'D': {'daughter': ['F']}, 
    'E': {'daughter': ['G']}, 
    'F': {'daughter': ['H']}, 
    'G': {'daughter': [None]}, 
    'H': {'daughter': [None]} 
} 

print(bfs(d, 'A'))