如何查找所有不被其他任意现有集合包含的最小集合

问题描述 #

现有一批被划分到不同集合中的元素，集合之间可能存在非空交集，需要找出所有不被其余任意现有集合包含的集合。

示例演示 #

示例输入 #

• 元素：a、b、c、d
• 现有集合：{a,b,c}, {a, b}, {a}, {a,b,c,d}, {b,d,c}

示例输出 #

{a}、{b,d,c}

推导逻辑 #

• {a,b,c,d} 包含 {a,b,c}，{a,b,c} 包含 {a, b}，{a, b} 包含 {a}
• {a,b,c,d} 包含 {b,d,c}

实现思路 #

通过构建有向图完成筛选：

• 所有节点对应输入的现有集合
• 若集合1包含于集合2，则在集合1和集合2之间建立一条有向边
  构建完成后，入度为0的节点即为目标结果。

可运行代码 #

import networkx as nx

# 初始化有向图
G = nx.DiGraph()
# 新增集合节点（使用frozenset是因为普通集合不可哈希，无法作为图节点）
G.add_nodes_from([
    frozenset({'a', 'b', 'c'}),
    frozenset({'a', 'b'}),
    frozenset({'a'}),
    frozenset({'a', 'b', 'c', 'd'}),
    frozenset({'b', 'd', 'c'})
])
# 建立包含关系的有向边：n包含于m则生成边n→m
G.add_edges_from([(n, m) for n in G for m in G if n != m and n < m])
# 筛选入度为0的节点即为结果
print([n for n, in_degree in G.in_degree() if in_degree == 0])

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