我有一個這樣的 Python 字典：
dictionary = {
'r1': {
'val': 'r',
'sub': {
'a1': {
'val': 'a',
'sub': {
'b1': {
'val': 'b',
'sub': {}
}
}
},
'b1': {
'val': 'b',
'sub': {
'c1': {
'val': 'c',
'sub': {}
},
'a2': {
'val': 'a',
'sub': {
'c2': {
'val': 'c',
'sub': {}
},
}
},
'a3': {
'val': 'a',
'sub': {}
},
'b2': {
'val': 'b',
'sub': {}
},
'a4': {
'val': 'a',
'sub': {
'c3': {
'val': 'c',
'sub': {}
},
'd1': {
'val': 'd',
'sub': {}
}
}
}
}
}
}
}
}
將字典解釋為一棵樹，我需要做的是找到最大回圈子樹。
對于最大回圈子樹，我的意思是例如：
subtree = {
'structure': {
'r': {
'sub': {
'b': {
'sub': {
'a': {
'sub': {
'c': {
'sub': {}
},
}
},
}
}
}
}
},
'counter': 2
}
基本上我正在嘗試實作一個遞回函式，如：
def find_max_subtree(dict: tree, dict: output) -> dict:
for key in tree:
...
output[key] = {
'sub' = {}
}
output[key]['sub'] = find_max_subtree(key['sub'], output['sub'])
return output
我不知道如何解決它。即使是偽代碼策略對我來說也足夠了。
uj5u.com熱心網友回復：
您可以在遞回時保留一個深度計數器，并在每個級別回傳具有最大關聯計數器的子字典：
def max_subtree(d, c = 0):
a, c_d, b = max([(a, c, b) if not b else (a, *max_subtree(b, c 1))
for a, b in d.items()], key=lambda x:x[1])
return (c_d, {a:b})
_, sub_dict = max_subtree(dictionary)
輸出：
{'r': {'sub': {'b': {'sub': {'a': {'sub': {'c': {'sub': {}}}}}}}}}
from collections import Counter
def build_dict(d):
return {} if not d else {d[0]:{'sub':build_dict(d[1:])}}
def get_paths(d, c = []):
if 'sub' not in d:
yield from [j for i in d.values() for j in get_paths(i,c)]
elif not d['sub']:
yield tuple(c [d['val']])
else:
for _, b in d['sub'].items():
yield from get_paths(b, c [d['val']])
result = Counter(get_paths(dictionary))
c = max(result, key=lambda x:[result[x] > 1, result[x], len(x)])
print(build_dict(c), result[c])
輸出：
{'r': {'sub': {'b': {'sub': {'a': {'sub': {'c': {'sub': {}}}}}}}}} 2
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/422810.html
標籤：