给定一个集合列表，我想得到一个相互交叉的集合列表列表。基本上我想要的是列表列表 s.t.对于输出中的每个列表，该列表中的所有集合都与同一列表中的至少另一个集合有一个非空交集。
我希望我能够解释我的问题。希望下面的示例和帖子的其余部分应该进一步阐明它。
给定，
sets = [
set([1,3]), # A
set([2,3,5]), # B
set([21,22]), # C
set([1,9]), # D
set([5]), # E
set([18,21]), # F
]
我想要的输出是:
[
[
set([1,3]), # A, shares elements with B
set([2,3,5]), # B, shares elements with A
set([1,9]), # D, shares elements with A
set([5]), # E shares elements with B
],
[
set([21,22]), # C shares elements with F
set([18,21]), # F shares elements with C
]
]
输出中集合的顺序无关紧要。
我想用一个非常快的算法来实现这个目标。性能是我的第一要求。
目前，我的解决方案创建了一个图，其中的节点数与原始列表中的集合数一样多。然后它在表示集合 A 和 B 的节点之间在此图中创建一条边，前提是这些集合具有非空交集。然后它计算了这样一个图的连通分量，这给了我预期的结果。
我想知道是否有更快的方法使用不涉及图形的算法来执行此操作。
最好的， 安德里亚
请您参考如下方法:
正如@MartijnPieters 所说的那样，问题需要图表，而networkx会帮你的。
要点
- 图中的节点应该是集合
- 图之间的边存在当且仅当集合相交
- 从结果图中，找到所有 connected components
实现
def intersecting_sets(sets):
import networkx as nx
G = nx.Graph()
# Nodes of the graph should be hashable
sets = map(frozenset, sets)
for to_node in sets:
for from_node in sets:
# off-course you don't want a self loop
# and only interested in intersecting nodes
if to_node != from_node and to_node & from_node:
G.add_edge(to_node, from_node)
# and remember to convert the frozen sets to sets
return [map(set, lst) for lst in nx.connected_components(G)]
输出
>>> intersecting_sets(sets)
[[set([2, 3, 5]), set([1, 3]), set([5]), set([1, 9])], [set([21, 22]), set([18, 21])]]
>>> pprint.pprint(intersecting_sets(sets))
[[set([2, 3, 5]), set([1, 3]), set([5]), set([1, 9])],
[set([21, 22]), set([18, 21])]]
