Let's say here is input:
input = {1:[2,3], 2:[], 3:[4,5,6], 4:[], 5:[], 6:[]}
This can be represented like below: tree
If all leaf nodes are 1, we can change like this:
for idx, val in input[1]:
if len(input[val]) == 0:
input[1][idx] = [] # input[1] = [[], 3]
else:
input[1][idx] = input[val] # input[1] = [[], [4,5,6]]
And then somehow, input[1]
can be input[1] = [[],[[],[],[]]]
.
So finally, i wanna get multiple numbers of each dict key elements compared to leaf nodes.
I am not sure the description that i wrote is clear.
Anyways, What i want get is like:
# 2, 4, 5, 6 are all leaf nodes.
# 3 is including [4, 5, 6] which are all leaf nodes, then 3's value must be 3 (len[4,5,6])
# 1 is including [2, 3]. Among them, only 2 is leaf. And 3's value is 3. So output[1] = 1 3 = 4
output = {1:4, 2:1, 3:3, 4:1, 5:1, 6:1}
CodePudding user response:
Simple recursion with functools.lru_cache
:
from functools import lru_cache
def leaves_count(tree):
@lru_cache
def cntr(key):
value = tree[key]
return sum(map(cntr, value)) if value else 1
return {k: cntr(k) for k in tree}
Test:
>>> tree = {1: [2, 3], 2: [], 3: [4, 5, 6], 4: [], 5: [], 6: []}
>>> leaves_count(tree)
{1: 4, 2: 1, 3: 3, 4: 1, 5: 1, 6: 1}
Manually implement the cached version:
def leaves_count(tree):
def cntr(key):
cnt = cache.get(key)
if cnt:
return cnt
value = tree[key]
cache[key] = cnt = sum(map(cntr, value)) if value else 1
return cnt
cache = {}
return {k: cntr(k) for k in tree}
CodePudding user response:
Using recursion method
Code:
dic= {1:[2,3], 2:[], 3:[4,5,6], 4:[], 5:[], 6:[]}
def recur(val, leaf):
for v in val:
if v in dic.keys():
if len(dic[v])==0:
leaf.append(v)
else:
recur(dic[v],leaf)
else:
leaf.append(v)
return len(leaf)
{key : 1 if recur(val,[])==0 else recur(val,[]) for key,val in dic.items()}
Output:
{1: 4, 2: 1, 3: 3, 4: 1, 5: 1, 6: 1}
Input: {1:[2,3], 2:[], 3:[4,5,6], 4:[], 5:[], 6:[7,8], 7:[], 8:[9,10], 9:[]}
Output: {1: 6, 2: 1, 3: 5, 4: 1, 5: 1, 6: 3, 7: 1, 8: 2, 9: 1}