如何合并有交集的集合(连通分量算法)? [英] How to merge sets which have intersections (connected components algorithm)?
问题描述
是否有任何有效的方法来合并具有交集的集合.例如:
Is there any effective way to merge sets which have intersections. For example:
l = [{1, 3}, {2, 3}, {4, 5}, {6, 5}, {7, 5}, {8, 9}]
预期结果是:
r = [{1, 2, 3}, {4, 5, 6, 7}, {8, 9}]
所有具有交集(公共分量)的集合都应合并.例如:
All sets which have intersection (common components) should be merged. For example:
{1, 3} & {2, 3}
# {3}
因此这两个集合应该合并:
So these two sets should be merged:
{1, 3} | {2, 3}
# {1, 2, 3}
不幸的是,我没有任何有效的解决方案.
Unfortunately I don't have any working solution.
更新:结果中集的顺序并不重要.
UPDATE: The order of sets in the result is not important.
推荐答案
一种有效的方法来实现是将集合列表转换为可散列的冻结集的集合,以便在迭代过程中找到与当前集合相交的冻结集.从池中将其删除:
An efficient way to implement the connected components algorithm as mentioned by @mkrieger1 in the comments is to convert the list of sets to a set of hashable frozensets so that as you iterate through it and find a frozenset that intersects with the current one you can easily remove it from the pool:
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}]
这篇关于如何合并有交集的集合(连通分量算法)?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!