我正在嘗試遍歷一個多層次、多層次的字典。我有一個 org char （字典），其中鍵作為人名，值作為其中之一None或帶有另一個組織結構圖的字典。
如果該名稱具有除“領導者”之外的任何值None，否則，它們是“非領導者”。每個一級字典名都是領導的直接下屬，進一步通過嵌套字典是領導的間接下屬。
給定一個名稱（字串）和一個 org_chart（嵌套字典），我想實作一個函式lookup_info，它輸出名稱是“領導”還是“非領導”，他們有多少直接下屬，以及有多少他們有間接報告。
我對 Python 并不陌生，但我被困在遍歷（這是 BFS 還是 DFS）以及如何在這里使用遞回。
這是一個例子：
ORG_CHART = {
"chloe" : {
"mark" : {
"tim" : {
"varun" : None,
"misha" : None
}
},
"julie" : None
},
"annie" : {
"jimmy" : {
"haily" : None,
"alex" : None
},
"helen" : {
"miley" : {
"stella" : {
"allie" : None
},
"tom" : None
}
}
},
"jenny" : None
}
def lookup(name, org_chart):
#TODO
return leadership_type, num_direct_reports, num_total_reports
name = "annie"應該輸出："leader", 2, 8
因為安妮有人向她匯報，所以她是領導者。她的價值觀直接有 2 個人，因此有 2 個直接下屬，總共有 8 個人在她手下作業。
name = "tom"應該輸出："non-leader", 0, 0
name = "miley"應該輸出"leader", 2, 3
我嘗試了以下方法來遞回嵌套字典（實際上還沒有獲得任何資訊，但只是試圖首先在字典中找到值，因為計數是下一步），但我被困在這第一步. None如果它到達第一級之上的任何級別，但它沒有字典作為它的值，它當然會回傳。
def lookup_info(name, org_chart):
def get_name_value(name, org_chart):
if org_chart != None:
for k, v in org_chart.items():
if k == name:
return k
else:
if v != None:
for i, j in v.items():
get_name_value(name, j)
name = get_name_value(name, org_chart)
return name
有什么想法請告訴我，謝謝！
uj5u.com熱心網友回復：
一個快速而骯臟的解決方案是定義一些其他輔助函式，并通過org_chart物件遞回：
def lookup(name: str, org_chart: dict):
it = _in(name, org_chart)
if not it:
return 'non-leader', 0, 0
return 'leader', len(it), _count(it)
def _count(o: dict):
if not o:
return 0
return len(o) sum(_count(v) for v in o.values())
def _in(name: str, o: dict):
if not o:
return None
if name in o:
return o[name]
for v in o.values():
res = _in(name, v)
if res:
return res
return None
用法：
ORG_CHART = {
"chloe": {
"mark": {
"tim": {
"varun": None,
"misha": None
}
},
"julie": None
},
"annie": {
"jimmy": {
"haily": None,
"alex": None
},
"helen": {
"miley": {
"stella": {
"allie": None
},
"tom": None
}
}
},
"jenny": None
}
print(lookup('annie', ORG_CHART))
print(lookup('miley', ORG_CHART))
print(lookup('tom', ORG_CHART))
出去：
('leader', 2, 8)
('leader', 2, 3)
('non-leader', 0, 0)
uj5u.com熱心網友回復：
遞回有點棘手，無法繞開大腦，所以這里有一個更詳細的選項，它以人類可讀的方式逐步完成整個程序。
請注意，這不考慮重復或其他邊緣情況，當然也不是最短或最有效的方法，但我認為它應該很好地為您服務，作為一個很好的起點。
def lookup_info(name, org_chart):
# some local variables to hold our results
leadership_type = None
num_direct_reports = 0
num_total_reports = 0
def helper(obj, depth):
# declare our intent to use the variables from above as nonlocals
nonlocal leadership_type, num_direct_reports, num_total_reports
# if the value is None, we hit a leaf and should return
if obj is None:
return
# otherwise, iterate through the key value pairs
for key, value in obj.items():
# if we see the name in the keys, we proceed accordingly
if key == name:
if value is not None:
# mark as a leader, and recurse with increased depth noted in param
leadership_type = "leader"
helper(obj=value, depth=depth 1)
else:
# otherwise this is a non-leader, we can return
leadership_type = "non-leader"
return
elif depth == 1:
# at depth 1 we handle direct subordinates, and recurse
num_direct_reports = 1
num_total_reports = 1
helper(obj=value, depth=depth 1)
elif depth > 1:
# at depth > 1 we handle indirect subordinates, and recurse
num_total_reports = 1
helper(obj=value, depth=depth 1)
else:
# here we continue checking deeper into the structure to cover all other cases from depth 0
helper(obj=value, depth=0)
# run our helper with the appropriate defaults to start
helper(obj=org_chart, depth=0)
# finally return the thruple
return leadership_type, num_direct_reports, num_total_reports
uj5u.com熱心網友回復：
如果計算成本是一個問題，并且您希望與大量個人一起呼叫您的函式，我寧愿建議掃描一次整個ORG_CHART并將結果值保存在一個新的值中，dict如下所示：
def reports(d):
ret = {} # reports of curent node
for k in d: # iterate on children
if d[k] is None:
ret[k] = [0, 0] # if None direct and indirect reports are 0
else:
d_child = reports(d[k])
ret = {
**ret, # current dict
**d_child, # merge with children one
k : [len(d[k]), sum(sum(d_child[s]) for s in d[k])] # direct is the number of children, indirect is sum of (children direct and indirect reports)
}
return ret
計算結果，輸出格式為 的目錄name -> [direct reports, indirect reports]。請注意，我沒有添加“領導者”欄位，因為它與直接下屬數量為0.
結果函式令人困惑，但最終非常簡潔。
mapping = reports(ORG_CHART)
print(mapping)
輸出：
{'varun': [0, 0],
'misha': [0, 0],
'tim': [2, 0],
'mark': [1, 2],
'julie': [0, 0],
'chloe': [2, 3],
'haily': [0, 0],
'alex': [0, 0],
'jimmy': [2, 0],
'allie': [0, 0],
'stella': [1, 0],
'tom': [0, 0],
'miley': [2, 1],
'helen': [1, 3],
'annie': [2, 6],
'jenny': [0, 0]}
完成此步驟后，您可以在 O(1) 中訪問結果。
只是為了好玩，下面是上述函式的更簡潔版本
def reports(d):
ret = {}
for k in d:
ret = {**ret, **reports(d[k])} if d[k] is not None else ret
ret[k] = [len(d[k]), sum(sum(ret[s]) for s in d[k])] if d[k] is not None else [0,0]
return ret
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/513472.html
上一篇：從整數的ArrayList中遞回洗掉相鄰的重復項，而不洗掉兩者
下一篇：從物件轉換物件組合