我有一個串列字典，其值是與同一字典中其他鍵的連接。我需要一個所有鍵之間連接的匯總串列，無論鍵彼此相距多少級。
我可以使用一堆不斷搜索同一個字典的 for 回圈來完成這項作業，但我不能讓它作為一個組合所有串列的遞回函式作業。
輸入：
sampleDict = {'1': ['2', '3'],
'2': ['1', '4'] ,
'3': ['1'],
'4': ['2'],
'5': ['6'],
'6': ['5', '7'],
'7': ['6', '8', '9'],
'8': ['7', '10'],
'9': ['7', '11'],
'10': ['8'],
'11': ['9'],
'12': [],
'13': ['14'],
'14': ['13']
}
預期輸出：
outputDict = {1: ['1', '2', '3', '4'],
2: ['5', '6', '7', '8', '9', '10', '11'],
3: ['12'],
4: ['13', '14']
}
我嘗試過的事情：
如果我運行此代碼塊的次數足夠多，我就會得到我想要的答案，然后對字典進行重復資料洗掉。但我更喜歡更動態的東西，可以適應不同的情況和鍵之間的連接數量。
for i in sampleDict.keys():
linked = sampleDict[i]
for j in linked:
sampleDict[i] = list(set(sampleDict[i] sampleDict[j]))
如果我將上面的代碼粘貼在遞回函式中，它會永遠運行，因為我找不到在每個連接建立后都適用的動態退出條件。
def clusters(dictionary):
for i in dictionary.keys():
linked = dictionary[i]
for j in linked:
dictionary[i] = list(set(dictionary[i] dictionary[j]))
return clusters(dictionary)
uj5u.com熱心網友回復：
這是使用深度優先搜索的解決方案。
def dfs(v,component,unseen,adj):
for w in adj[v]:
if w in unseen:
component.append(w)
unseen.remove(w)
dfs(w,component,unseen,adj)
unseen = set(sampleDict)
components = []
while unseen:
v = unseen.pop()
components.append([v])
dfs(v,components[-1],unseen,sampleDict)
components.sort()
outputDict = dict(enumerate(components))
結果outputDict由下式給出
{0: ['4', '2', '1', '3'],
1: ['14', '13'],
2: ['6', '5', '7', '8', '10', '9', '11'],
3: ['12']}
uj5u.com熱心網友回復：
你可以試試：
sampleDict = {
"1": ["2", "3"],
"2": ["1", "4"],
"3": ["1"],
"4": ["2"],
"5": ["6"],
"6": ["5", "7"],
"7": ["6", "8", "9"],
"8": ["7", "10"],
"9": ["7", "11"],
"10": ["8"],
"11": ["9"],
"12": [],
"13": ["14"],
"14": ["13"],
}
tmp = {}
for k, v in sampleDict.items():
tmp.setdefault(k, set())
tmp[k].add(k)
for vv in v:
tmp.setdefault(vv, tmp[k])
tmp[k].add(vv)
print(dict(enumerate({id(v): v for v in tmp.values()}.values(), 1)))
印刷：
{
1: {"2", "4", "1", "3"},
2: {"6", "7", "10", "8", "5", "9", "11"},
3: {"12"},
4: {"13", "14"},
}
如果您想要輸出串列而不是集合，那么作為最后一步：
print(
dict(
enumerate({id(v): sorted(v, key=int) for v in tmp.values()}.values(), 1)
)
)
印刷：
{
1: ["1", "2", "3", "4"],
2: ["5", "6", "7", "8", "9", "10", "11"],
3: ["12"],
4: ["13", "14"],
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/528635.html
標籤：Python列表字典递归