How To Get All Children, Grandchildren, ... From This List?

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,

Solution 1:

You may try this:

tree = {}

foritemin items:
    parent = item['id']
    child = [it['id'] foritin items if it['parent'] == parent]
    grandchild = [it['id'] forcin child foritin items if it['parent'] == c]
    tree[parent] = [*child, *grandchild]

print(tree)

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

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.

EDIT:

For:

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

Code:

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)

Output:

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

Solution 2:

First off, your while loop is useless as you will always break at the end of it.

In order to get the grandchildren, you would need to duplicate the

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

check inside of itself to handle the grandparent. If you wanted to generalize your code to handle any level, you would need to keep duplicating that block inside of itself for each additional level you wanted to handle.

If such generalization may be required, a recursive approach would be easiest, such as the following code, which also includes a pre-process step to simplify and optimize the later code:

defgetChildrenRecursive(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

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

    parent = item['parent']
    if parent isNone:
        return

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

Note that the code can be converted to a non-recursive version fairly easily as it does only use a tail-call, but I will leave that as an exercise to the reader.

For just getting the children and grand-children, it would be called like:

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.

Solution 3:

Here is another solution:

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}


defcrawl_relations(relatives):
    iflen(relatives) andlen(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'] isnotNone:
        families[item['parent']].append(item['id'])

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

print(families)

Solution 4:

Here you 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 ifidin 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) forid, _ in ancestors}
print(descendents)

Solution 5:

You can try using:

if not change:
    continue

break will simply break the iteration from the while loop.