2017-05-30 62 views
0

我有一本鏈接父母女兒衰變鏈中各種物種的字典。例如:使用遞歸構建大字典的子字典

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時,這被認爲是鏈條的結束。

我想要一個函數根據用戶輸入的起始父項返回包含鏈中項目的子字典。我也想知道鏈中每件商品的位置。在子字典中,這可以是第二個字段('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']}} 

這是比較容易的時候,該鏈接爲一個對一個,即一個項目衰變爲另一種,到另一個等

如果我現在使用更復雜的例子,下面,你可以看到 'B'實際上衰變爲'C'和'D',並且從那裏起,鏈是分開的。

A => B => C => E => G和A => B => d => F =>ħ

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]} 
} 

在這種情況下,我想一個函數來返回以下輸出。你會注意到,由於這兩條鏈的轉移,位置值接近例如heirachy的水平。 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']} 
} 

有什麼想法?該功能應該能夠應對鏈中多個轉向。

馬克

+0

谷歌的深度優先搜索 – e4c5

+0

我不認爲我是什麼定義名稱爲'list'? – Mark

回答

0

如果你不想去,一路由C下來,然後breadth-first search可能會有幫助。

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'))