Как вытащить всех детей, внуков, ... из этого списка?

Question

У меня items в отношениях родитель-ребенок. Каждый ребенок знает своего родителя, но родитель не знает ни своих детей, ни своих внуков:

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

Я пытаюсь создать диктовку, которая включает все идентификаторы предметов со списком всех его детей, внуков и и так далее:

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

Мой текущий подход учитывает только детей, а не внуков:

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: []
}

Есть идеи? Заранее спасибо!

Answer 1

Здесь вы go:

parents_of_children = {item['id']: item['parent'] for item in items}

def find_ancestors(child: int) -> Tuple[int, List[int]]:
  def _find_ancestors(_id: int, family: List[int]):
    if not parents_of_children[_id]:
      return child, family
    else:
      return _find_ancestors(parents_of_children[_id], family + [parents_of_children[_id]])

  return _find_ancestors(child, [])


def find_descendents(id: int, ancestors: List[Tuple[int, List[int]]]) -> List[int]:
  family_trees = [[child] + ancestors_of_child for child, ancestors_of_child in
                  ancestors if id in ancestors_of_child]
  return [child for child in
          takewhile(lambda i: i != id, max(family_trees) if family_trees else [])][::-1]


ancestors = [find_ancestors(child) for child in parents_of_children]
descendents = {id: find_descendents(id, ancestors) for id, _ in ancestors}
print(descendents)

Answer 2

Вот еще одно решение:

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

families = {item['id']: [] for item in items}


def crawl_relations(relatives):
    if len(relatives) and len(families[relatives[0]]) and families[relatives[0]][0] != relatives[-1]:
        crawl_relations(families[relatives[0]])
        relatives += families[relatives[0]]


for item in items:
    if item['parent'] is not None:
        families[item['parent']].append(item['id'])

for relatives in families.values():
    crawl_relations(relatives)

print(families)

Answer 3

Вы можете попробовать это:

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 как дочерний элемент, так же как и мой код.

Код может быть дополнительно оптимизирован и модифицирован для более общих случаев использования. Я оставляю это вам, как считаете нужным.

РЕДАКТИРОВАТЬ:

Для:

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: []}

Answer 4

Прежде всего, ваше время l oop бесполезно, так как вы всегда сломаете его в конце.

Чтобы получить внуков, вам нужно будет продублировать

    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'])

проверьте внутри себя, чтобы справиться с дедушкой. Если вы хотите обобщить свой код для обработки любого уровня, вам нужно будет повторять этот блок внутри себя для каждого дополнительного уровня, который вы хотите обработать.

Если такое обобщение может потребоваться, рекурсивный подход будет самый простой, такой как следующий код, который также включает в себя этап предварительной обработки для упрощения и оптимизации более позднего кода:

def getChildrenRecursive(items, maxLevel):
    ''' Returns a dict of item IDs and a list of their children up to maxLevel deep. '''
    itemsByID = {}
    result = {}
    for item in items:
        result[item['id']] = []
        itemsByID[item['id']] = item

    for item in items:
        walkParents(result, item, itemsByID, item['id'], 1, maxLevel)

    return result

def walkParents(result, item, items, idToAdd, level, maxLevel):
    if level > maxLevel:
        return

    parent = item['parent']
    if parent is None:
        return

    result[parent].append(idToAdd)
    parentItem = items[parent]
    walkParents(result, parentItem, items, idToAdd, level + 1, maxLevel)

Обратите внимание, что код может быть преобразован в нерекурсивную версию довольно легко, так как использует только хвостовой вызов, но я оставлю это в качестве упражнения для читателя.

Для того, чтобы просто получить детей и внуков, это будет называться как:

items = [
  {'id': 1, 'parent': None},
  {'id': 2, 'parent': 1},
  {'id': 3, 'parent': 2},
  {'id': 4, 'parent': None},
  {'id': 5, 'parent': 4},
]
getChildrenRecursive(items, 2) # Returns the result. The number is the maximum number of steps to walk.

Answer 5

Вы можете попробовать использовать:

if not change:
    continue

break просто прервет итерацию от while l oop.