是否有任何有效的方法来合并具有交集的集合。例如:
l = [{1, 3}, {2, 3}, {4, 5}, {6, 5}, {7, 5}, {8, 9}]
预期的结果是:
r = [{1, 2, 3}, {4, 5, 6, 7}, {8, 9}]
应合并所有具有交集(公共(public)组件)的集合。例如:
{1, 3} & {2, 3}
# {3}
所以这两个集合应该合并:
{1, 3} | {2, 3}
# {1, 2, 3}
很遗憾,我没有任何可行的解决方案。
更新:结果中集合的顺序并不重要。
实现 connected components algorithm 的有效方法正如 @mkrieger1 在评论中提到的那样,将集合列表转换为一组可散列的卡住集,以便在您遍历它并找到与当前卡住集相交的卡住集时,您可以轻松地将其从池中删除:
pool = set(map(frozenset, l))
groups = []
while pool:
groups.append(set(pool.pop()))
while True:
for candidate in pool:
if groups[-1] & candidate:
groups[-1] |= candidate
pool.remove(candidate)
break
else:
break
给定 l = [{1, 3}, {2, 3}, {4, 5}, {6, 5}, {7, 5}, {8, 9}]
, groups
将变为:
[{1, 2, 3}, {4, 5, 6, 7}, {8, 9}]
并且给定 l = [{1, 2}, {3, 4}, {2, 3}]
,groups
将变为:
[{1, 2, 3, 4}]
并且给定 l = [{1}, {2}, {1, 2}]
,groups
将变为:
[{1, 2}]