循环/递归来处理Python中的层次结构

Question

我想知道是否有一种更有效的方法可以循环通过一组对象，这些对象之间可能有一些依赖关系(父子关系(，例如：

dependencies = [(child1,parent1),(child2,parent2),...]
obj_stack    = [{'id':'child1'},{'id':'child2'},{'id':'parent1'},..]
new_stack    = [{'id':'child1'},{'id':'child3'}]
check_and_add_to_new_stack(obj) # function that decides if an obj should be added to the new stack

我想在两个条件下检查每个obj_stack并将obj添加到new_stack中：

• 它没有父级，check_and_add_to_new_stack(obj)添加了它(假设它做得正确(
• 它有一个父级，然后直接添加(不需要使用上面的函数(

这意味着我需要检查元素是否有父元素，然后检查&首先添加其父级。如果添加了它，那么我会回到那个元素。我有点陷入了递归循环。这是伪代码：

def check_and_add_to_new_stack(obj,stack):
   if passed_checks(obj):
     return add_to_new_stack(obj,stack)
   return stack
def myFunction(obj_stack, new_stack, dependencies):
  for obj in obj_stack:
    if obj is not in new_stack:
       if obj has parent in dependencies:
         myFunction([parent], new_stack, dependencies) 
       else: # here the original obj should be thrown back into the function
         new_stack += check_and_add_to_new_stack(obj)
  return stack

编辑：添加我期待的结果和更多详细信息：让我们假设

passed_checks(parent1) = False
passed_checks(parent2) = True
passed_checks(child1) = True
passed_checks(child2) = False

预期结果是：

myFunction(obj_stack, new_stack, dependencies)
> [{'id':'child1'},{'id':'child3'},{'id':'child2'},{'id':'parent2'}]

即使passed_checks(child2) = False，它也有一个parent2，其中passed_checks = True，所以两者都被添加到结果集。child1已在new_stack中。未添加parent1，因为passed_checks = False。

Answer 1

我想你可能正在寻找这样的东西。

• walk_ancestry基于parents dict(基本上是原始代码中的dict(dependencies)(为给定节点及其所有父节点生成节点ID
• check是你的检查函数——我刚刚把你的条件复制到那里
• all_passing集合理解迭代我们所有已知的对象名称(原始代码中的obj_stack(，并使用内置的any函数来查看该节点祖先中是否有任何节点通过了check()测试。如果是这样的话，就被认为是通过了

通过缓存和内存化可以更快地实现这一点，但对于足够小的图，我确信这一切都很好。

def walk_ancestry(parents, node):
    while True:
        yield node
        node = parents.get(node)
        if not node:
            break

def check(node):
    return node in {"parent2", "child1"}

parents = {
    "child1": "parent1",
    "child2": "parent2",
    "parent2": "parent3",
}
all_objects = {
    "parent1",
    "parent2",
    "parent3",
    "child1",
    "child2",
}
all_passing = {
    node
    for node in all_objects
    if any(check(n) for n in walk_ancestry(parents, node))
}
print(all_passing)

输出为

['parent2', 'child2', 'child1']