给定相关数字列表,合并相关列表以创建不相交集 [英] Given lists of related numbers, merge related lists to create disjoint sets
问题描述
给出:
[(1,2),(3,4),(5,6),(3,7),(5,7)]
输出:
[set(1,2), set(3,4,5,6,7)]
说明:
(1,2)
(1,2), (3,4)
(1,2), (3,4), (5,6)
(1,2), (3,4,7), (5,6)
(1,2), (3,4,7,5,6)
我写了一个糟糕的算法:
I have written a lousy algorithm:
Case 1: both numbers in pair are new (never seen before):
Make a new set with these two numbers
Case 2: one of the number in pair is new, other is already a part of some set:
Merge the new number in other's set
Case 3: both the numbers belong to some set:
Union the second set into first. Destroy the second set.
此算法是否还有更多的pythonic(奇特的)解决方案?
Is there a more pythonic (fancy) solution to this algo?
推荐答案
您可以使用 Unionfind算法.首先,我们使用字典从这些对中创建一棵树:
You can use the Unionfind algorithm for this. First, we are using a dictionary to create a tree from the pairs:
leaders = collections.defaultdict(lambda: None)
现在我们使用两个函数-union
和find
-填充该树:
Now we use two functions -- union
and find
-- to populate that tree:
def find(x):
l = leaders[x]
if l is not None:
l = find(l)
leaders[x] = l
return l
return x
def union(x, y):
lx, ly = find(x), find(y)
if lx != ly:
leaders[lx] = ly
只需遍历所有对,然后将它们放入树中即可.
Just iterate over all the pairs and put them into the tree.
for a, b in [(1,2),(3,4),(5,6),(3,7),(5,7)]:
union(a, b)
它看起来像这样:{1: 2, 2: None, 3: 4, 4: 7, 5: 6, 6: 7, 7: None}
最后,我们将数字按其各自的领导者"分组,即find
返回的内容:
Finally, we group the numbers by their respective "leaders", i.e. what is returned by find
:
groups = collections.defaultdict(set)
for x in leaders:
groups[find(x)].add(x)
现在,groups.values()
是[set([1, 2]), set([3, 4, 5, 6, 7])]
复杂度应约为 O(nlogn).
这篇关于给定相关数字列表,合并相关列表以创建不相交集的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!