递归查找 child 给定字典列表的所有 parents

Question

给定字典列表如下：

[{'id': '1', 'parents': []},
 {'id': '2', 'parents': ['1']},
 {'id': '3', 'parents': ['1', '2']},
 {'id': '4', 'parents': ['3']},
 {'id': '5', 'parents': ['1', '2', '3', '4']},
 {'id': '6', 'parents': ['4', '5']},
 {'id': '7', 'parents': ['4']},
 {'id': '8', 'parents': []},
 {'id': '9', 'parents': ['1', '8']},
 {'id': '10', 'parents': ['8']},
 {'id': '11', 'parents': ['5', '6']}]

我想构建一个递归结束返回所有元素的函数 parents。

例如元素 11 有两个 parents, 5 和 6 也分别有 ['1', '2', '3', '4'] 和 ['4','5' ] 其中还有…… 所以在这种情况下 11 的总 parents 是 [1,2,3,4,5,6]

我从这样的事情开始：

def total_parents(parentlist,tree):
    if parentlist == []:
        return
    total = []
    for parent in parentlist:
        total.append(next((element['parents'] for element in tree if element['id'] == parent), None))
    total_flatten = [item for sublist in total for item in sublist]
    total_flatten_set = list(set(total_flatten))
    return total_parents(total_flatten_set,tree)

for claim in tree:
    claim['total_parents'] = total_parents(claim['parents'],tree)

这根本行不通。在玩了很多代码并查看了一些递归问题之后：How to recursively generate a list of parent-child strings from an Adjacency List?

Answer 1

您可以使用递归生成器函数：

data = [{'id': '1', 'parents': []}, {'id': '2', 'parents': ['1']}, {'id': '3', 'parents': ['1', '2']}, {'id': '4', 'parents': ['3']}, {'id': '5', 'parents': ['1', '2', '3', '4']}, {'id': '6', 'parents': ['4', '5']}, {'id': '7', 'parents': ['4']}, {'id': '8', 'parents': []}, {'id': '9', 'parents': ['1', '8']}, {'id': '10', 'parents': ['8']}, {'id': '11', 'parents': ['5', '6']}]
d = {i['id']:i for i in data}
def get_ids(_id, c = []):
   yield from d[_id]['parents']
   for i in filter(lambda x:x not in c+[_id], d[_id]['parents']):
      yield from get_ids(i, c+[_id])

r = [{**i, 'total_parents':sorted(set(get_ids(i['id'])))} for i in data]

输出：

[{'id': '1', 'parents': [], 'total_parents': []}, 
 {'id': '2', 'parents': ['1'], 'total_parents': ['1']}, 
 {'id': '3', 'parents': ['1', '2'], 'total_parents': ['1', '2']}, 
 {'id': '4', 'parents': ['3'], 'total_parents': ['1', '2', '3']}, 
 {'id': '5', 'parents': ['1', '2', '3', '4'], 'total_parents': ['1', '2', '3', '4']}, 
 {'id': '6', 'parents': ['4', '5'], 'total_parents': ['1', '2', '3', '4', '5']}, 
 {'id': '7', 'parents': ['4'], 'total_parents': ['1', '2', '3', '4']}, 
 {'id': '8', 'parents': [], 'total_parents': []}, 
 {'id': '9', 'parents': ['1', '8'], 'total_parents': ['1', '8']}, 
 {'id': '10', 'parents': ['8'], 'total_parents': ['8']}, 
 {'id': '11', 'parents': ['5', '6'], 'total_parents': ['1', '2', '3', '4', '5', '6']}]

Answer 2

Given a dictionary as follows:

您输入的不是字典。这是一个 list 包含 2 元素字典（其中包含大量冗余信息）。如果您可以重新格式化您的输入，那么您正在寻找的功能就非常简单了。

如果您的输入是以下形式的字典，您可以按照以下方式构建函数：{<id>: [<parents>]}:

parent_map ={
    '1': [],
    '2': ['1'],
    '3': ['1', '2'],
    '4': ['3'],
    '5': ['1', '2', '3', '4'],
    '6': ['4', '5'],
    '7': ['4'],
    '8': [],
    '9': ['1', '8'],
    '10': ['8'],
    '11': ['5', '6']}

def get_parents(parent_map, node_id):
    parents = set(parent_map[node_id])
    for parent_id in parent_map[node_id]:
        parents |= set(get_parents(parent_map, parent_id))
    return list(parents)

下面是将原始输入数据转换为上述函数中使用的格式的方法：

single_dict = {x['id']: x['parents'] for x in list_of_dicts}

输入数据的形状和格式对您对其进行操作的效率有着巨大的影响。

递归查找 child 给定字典列表的所有 parents

Recursively find all the parents of a child given list of dictionaries

python

recursion

tree

parent-child