如何判断给定元素集合能否共同生成指定父元素？

我有一个存储元素及其依赖子元素的Python字典，示例如下：

product_dict = {
    'A': {'B', 'C', 'D'},
    'B': {'E', 'F'},
    'C': {'G'},
    'D': {},
    'E': {'H', 'I'}
}

根据这个字典的规则：

• 若集合包含B、C、D，就能生成A；
• 若集合包含E、F、G、D，也能生成A（因为B可由E+F生成）；
• 若集合包含H、I、F、G、D，同样能生成A（因为E可由H+I生成）。

现在需要编写一个Python函数，判断给定的元素集合是否能够生成指定的目标元素（比如判断{'H','I','F','G','D'}能否生成'A'）。除了递归方案，也希望了解其他可用算法。

方法1：递归实现 #

递归的核心逻辑很直观：

1. 如果目标元素已经在给定集合里，直接返回True；
2. 如果目标元素没有子元素（即依赖为空），说明必须直接提供该元素，返回False；
3. 否则，检查目标元素的所有子元素是否都能被当前集合生成——对每个子元素递归调用判断函数，只有全部子元素都满足条件，才返回True。

代码实现：

def can_generate_recursive(target, available, product_dict):
    # 目标元素已在可用集合中，直接返回True
    if target in available:
        return True
    # 目标元素没有依赖，但不在可用集合中，无法生成
    if not product_dict.get(target, set()):
        return False
    # 检查所有子元素是否都能被生成
    return all(can_generate_recursive(child, available, product_dict) 
               for child in product_dict[target])

测试示例：

available = {'H','I','F','G','D'}
print(can_generate_recursive('A', available, product_dict))  # 输出: True
print(can_generate_recursive('B', {'E', 'F'}, product_dict))  # 输出: True
print(can_generate_recursive('C', {'F'}, product_dict))  # 输出: False

方法2：迭代式深度优先搜索（DFS） #

当字典的层级很深时，递归可能触发栈溢出错误，这时可以用迭代的DFS来模拟递归过程。我们维护一个待检查的元素栈，以及一个记录“已确认可生成”的集合，逐步把能生成的元素加入集合，最终判断目标是否在其中。

代码实现：

def can_generate_dfs(target, available, product_dict):
    # 初始化已生成集合为可用元素的副本
    generated = set(available)
    stack = list(generated)
    
    while stack:
        current = stack.pop()
        # 遍历所有以current为子元素的父元素（即哪些元素依赖current）
        for parent, children in product_dict.items():
            if current in children and parent not in generated:
                # 检查该父元素的所有子元素是否都已生成
                if all(child in generated for child in children):
                    generated.add(parent)
                    stack.append(parent)
                    # 提前终止：如果目标已生成，直接返回True
                    if target in generated:
                        return True
    return target in generated

方法3：迭代式广度优先搜索（BFS） #

BFS和DFS逻辑类似，只是用队列代替栈，按层级处理元素，适合需要逐层推导的场景，同样能避免递归栈溢出的问题。

代码实现：

from collections import deque

def can_generate_bfs(target, available, product_dict):
    generated = set(available)
    queue = deque(generated)
    
    while queue:
        current = queue.popleft()
        for parent, children in product_dict.items():
            if current in children and parent not in generated:
                if all(child in generated for child in children):
                    generated.add(parent)
                    queue.append(parent)
                    if target in generated:
                        return True
    return target in generated

方法4：集合迭代更新法 #

还有一种更简洁的迭代思路：不断查找所有能被当前生成集合满足依赖的父元素，把它们加入生成集合，直到没有新元素可以加入为止，最后判断目标是否在集合中。

代码实现：

def can_generate_iterative(target, available, product_dict):
    generated = set(available)
    while True:
        # 找出当前所有能被生成的父元素
        new_generated = set()
        for parent, children in product_dict.items():
            if parent not in generated and all(child in generated for child in children):
                new_generated.add(parent)
        # 没有新元素可以生成，终止循环
        if not new_generated:
            break
        generated.update(new_generated)
        # 提前终止
        if target in generated:
            return True
    return target in generated

内容的提问来源于stack exchange，提问作者Frederico Portela