给定相关数字列表，合并相关列表以创建不相交集

本文介绍了给定相关数字列表，合并相关列表以创建不相交集的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

给出:

[(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).