计算家谱中的所有后代（python 字典）

Question

我有点头疼了，我希望 Whosebug 上的人能帮助我。假设我有一个 python 字典，看起来像：

{
    'Son1': 'Father',
    'Son2': 'Father',
    'Father': 'Grandfather',
    'Grandfather': 'Great Grandfather',
    'Uncle': 'Grandfather',
    'Cousin': 'Uncle',
}

对，所以每个键都是一个人，对应的值就是那个人的parent。我现在想做的就是找出给定的人有多少后代。我有一个非常简单的函数，可以找到并 returns 给定人的直接 children.

列表

def get_kids(person, dictionary):
    kids = []
    for key in dictionary:
        if dictionary[key] == person:
            kids.append(key)
    return kids

效果很好。从那里开始，我一直认为我需要做的就是编写一个类似于以下内容的递归函数：

def descendants(person, dictionary, count):
    kids = get_kids(person, dictionary)
    count = count + len(kids)
    for kid in kids:
         descendants(kid, dictionary, count)
    return count

但这不起作用。我认为是因为 'count' 变量在 'line' 后代的末尾重置，而不是运行ning 总数。例如如果我运行:

descendants('Grandfather', familydictionary, 0)

我得到一个值 2（而不是 hoped-for 5）。据推测，当函数探索 'Father' 行时，计数达到 4，但当它探索 'Uncle' 行时，计数又回落到 3。然后，我想，当函数发现 'Cousin' 没有孩子时，计数会一直下降到 2？我经常与这些递归问题作斗争。我想做的事情非常简单：检查一个人是否有孩子并计算他们，检查他们的孩子是否有孩子并计算他们，将他们添加到总数中......继续下去直到没有更多的孩子。但是，当我尝试实际编写执行此操作的代码时，我变得非常困惑。感谢任何帮助或指导。

Answer 1

您需要实际使用递归调用返回的值。在中传递 count 是没有必要或有用的。它是按值传递的，因此在递归的一个级别内更改它根本不会影响父调用。相反：

def descendants(person, dictionary): count = 0 for kid in get_kids(person, dictionary): count += 1 + descendants(kid, dictionary) return count

Answer 2

您需要对每个后代的后代求和。

>>> tree = {
...     'Son1': 'Father',
...     'Son2': 'Father',
...     'Father': 'Grandfather',
...     'Grandfather': 'Great Grandfather',
...     'Uncle': 'Grandfather',
...     'Cousin': 'Uncle',
... }
>>> def descendants(person: str, tree: dict[str, str]) -> int:
...     return sum(
...         1 + descendants(child, tree)
...         for child, parent in tree.items() 
...         if parent == person
...     )
...
>>> descendants("Father", tree)
2
>>> descendants("Grandfather", tree)
5

如果您想要实际后代的列表，您可以使用相同的基本结构，但对列表求和而不是对计数求和。这也使得更容易可视化求和如何导致递归情况的最终解决方案：

>>> def descendants(person: str, tree: dict[str, str]) -> list[str]:
...     return sum((
...         [child] + descendants(child, tree)
...         for child, parent in tree.items()
...         if parent == person
...     ), [])
...
>>> descendants("Father", tree)
['Son1', 'Son2']
>>> descendants("Uncle", tree)
['Cousin']
>>> descendants("Grandfather", tree)
['Father', 'Son1', 'Son2', 'Uncle', 'Cousin']

即：

descendants("Father", tree) == [] + ["Son1"] + ["Son2"]
descendants("Uncle", tree) == [] + ["Cousin"]
descendants("Grandfather", tree) == [] + ["Father"] + descendants("Father", tree) + ["Uncle"] + descendants("Uncle", tree)

Answer 3

您可以使用 treelib 使用库的方法实现您想要的结果。递归函数是遍历树结构的好方法，但为它们的工作奠定良好的基础非常有用。根据您将要构建的其他功能，treelib 确实可以派上用场，以避免重新发明轮子并在此过程中浪费时间。特别是如果你正在做的是一个家庭 tree.

Treelib 可以通过 pip install treelib 安装。

代码

>>> from treelib import Tree
>>> family = Tree()
>>> family.create_node("Great Grandfather", "Great Grandfather")  # root node
>>> family.create_node("Grandfather", "Grandfather", parent="Great Grandfather")
>>> family.create_node("Uncle", "Uncle", parent="Grandfather")
>>> family.create_node("Father", "Father", parent="Grandfather")
>>> family.create_node("Cousin", "Cousin", parent="Uncle")
>>> family.create_node("Son1", "Son1", parent="Father")
>>> family.create_node("Son2", "Son2", parent="Father")

>>> family.show() # tree.show() prints the tree in human-readable format

Great Grandfather
└── Grandfather
    ├── Father
    │   ├── Son1
    │   └── Son2
    └── Uncle
        └── Cousin

>>> def descendants(person, tree):
...     person_family = tree.subtree(person) # Create a subtree starting with person.
...     return person_family.size() - 1 # Subtracting 1 for Great Grandfather because tree.size() returns the total number of nodes in a tree.

>>> person = "Great Grandfather"
>>> print("{person} has {desc} descendants.".format(person=person, desc=descendants(person, family)))
Great Grandfather has 6 descendants.

>>> person = "Grandfather"
>>> print("{person} has {desc} descendants.".format(person=person, desc=descendants(person, family)))
Grandfather has 5 descendants.

>>> person = "Father"
>>> print("{person} has {desc} descendants.".format(person=person, desc=descendants(person, family)))
Father has 2 descendants.

计算家谱中的所有后代（python 字典）

Counting all descendants in a family tree (python dictionary)

python

recursion

dictionary

代码