如何从此列表中获取所有子孙... [英] How to get all children, grandchildren, ... from this list?

问题描述

我有items个父子关系.每个孩子都知道其父母，但父母不知道其子女或孙子:

I've items in a parent-child-relation. Every child knows its parent but a parent doesn't know its children nor its grandchildren:

items = [
  {'id': 1, 'parent': None},
  {'id': 2, 'parent': 1},
  {'id': 3, 'parent': 2},
  {'id': 4, 'parent': None},
  {'id': 5, 'parent': 4},
] 

我正在尝试构建一个包含所有项ID的字典，其中包含所有子项，孙子项等等的列表:

I'm trying to build a dict which includes all item ids with a list of all its children, grandchildren and so on:

all_children_of_items = {
  1: [2, 3],  # 2 = child, 3 = grandchild
  2: [3],
  3: [],
  4: [5],
  5: [6]
}

我目前的做法只考虑孩子，而不考虑孙子:

My current approach only considers the children, not the grandchildren:

all_children_of_items = {}
while True:
  change = False
  for item in items:
    if item['id'] not in all_children_of_items:
      all_children_of_items[item['id']] = []
    if item['parent']:
      if item['parent'] not in all_children_of_items:
        all_children_of_items[item['parent']] = []
      if item['id'] not in all_children_of_items[item['parent']]:
        all_children_of_items[item['parent']].append(item['id'])
  if not change:
    break

当前结果:

{
  1: [2], 
  2: [3], 
  3: [], 
  4: [5], 
  5: []
}

有什么主意吗?预先感谢！

Any idea? Thanks in advance!

推荐答案

您可以尝试以下方法:

tree = {}

for item in items:
    parent = item['id']
    child = [it['id'] for it in items if it['parent'] == parent]
    grandchild = [it['id'] for c in child for it in items if it['parent'] == c]
    tree[parent] = [*child, *grandchild]

print(tree)

输出: {1: [2, 3], 2: [3], 3: [], 4: [5], 5: []}

我看不到5如何将6作为孩子，所以我的代码也没有.

I do not see how 5 has 6 as child, so neither does my code.

可以对代码进行进一步优化，并针对更一般的用例进行修改.如果您认为合适，我会留给您.

The code can be further optimized, and modified for more general use cases. I leave that to you, as you see fit.

针对:

items = [{'id': 1, 'parent': None},
 {'id': 2, 'parent': 1},
 {'id': 3, 'parent': 2},
 {'id': 4, 'parent': 3},
 {'id': 5, 'parent': 4}]

代码:

def nepotism(parent):
    lineage = []
    def recurs(parent):
        for item in items:
            if item['parent'] == parent:
                possible_parent = item['id']
                lineage.append(possible_parent)
                recurs(possible_parent)
    recurs(parent)
    return lineage

tree = dict([(item['id'], nepotism(item['id'])) for item in items])
print(tree)

输出:

{1: [2, 3, 4, 5], 2: [3, 4, 5], 3: [4, 5], 4: [5], 5: []}

这篇关于如何从此列表中获取所有子孙...的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！