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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python-给定相关数字列表,合并相关列表以创建不相交集，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1218字，纯文字阅读大概需要2分钟。

内容图文

鉴于：

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

我写了一个糟糕的算法：

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(花式)解决方案对此算法？

解决方法:

您可以为此使用Unionfind algorithm.首先,我们使用字典从这些对中创建一棵树：

leaders = collections.defaultdict(lambda: None)

现在,我们使用两个函数(union和find)填充该树：

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

只需遍历所有对,然后将它们放入树中即可.

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,6：7,7：None}

最后,我们将数字按各自的“领导者”分组,即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).

内容总结

以上是互联网集市为您收集整理的python-给定相关数字列表,合并相关列表以创建不相交集全部内容，希望文章能够帮你解决python-给定相关数字列表,合并相关列表以创建不相交集所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端