将列表与交集合并

2022-01-17 00:00:00 python algorithm set

问题描述

鉴于:

g=[[], [], [0, 2], [1, 5], [0, 2, 3, 7], [4, 6], [1, 4, 5, 6], [], [], [3, 7]]

如何比较 g 中的每个列表，以便共享任何公共编号的列表可以合并到一个集合中?

How can I compare each list within g so that for lists sharing anyone common number can merge to a set?

例如
0 存在于 g[2] 和 g[4]所以它们合并到一个集合 {0,2,3,7}

e.g.
0 exists in g[2] and g[4] so they merge to a set {0,2,3,7}

我尝试了以下方法，但它不起作用:

I have tried the following but it doesn't work:

for i in g:
    for j in g:
        if k in i == l in j:
            m=set(i+j)

我想制作尽可能大的集合.

I want to make the largest possible set.

解决方案

作为一种快得多的方式，您可以先创建一个 len 大于一个 (s) .然后浏览您的列表并使用 union 功能！

As a much faster way You can first create a list of the set of items with len more than one (s) . then go through your list and update in place with union function ! 

s=map(set,g)
def find_intersection(m_list):
    for i,v in enumerate(m_list) : 
        for j,k in enumerate(m_list[i+1:],i+1):
           if v & k:
              m_list[i]=v.union(m_list.pop(j))
              return find_intersection(m_list)
    return m_list

演示:

g=[[], [], [0, 2], [1, 5], [0, 2, 3, 7], [4, 6], [1, 4, 5, 6], [], [], [3, 7]]
s=map(set,g)
print find_intersection(s)

[set([0, 2, 3, 7]), set([1, 4, 5, 6])]

g=[[1,2,3],[3,4,5],[5,6],[6,7],[9,10],[10,11]]
s=map(set,g)
print find_intersection(s)

[set([1, 2, 3, 4, 5, 6, 7]), set([9, 10, 11])]

g=[[], [1], [0,2], [1, 5], [0, 2, 3, 7], [4, 6], [1, 4, 5, 6], [], [], [3, 7]]
s=map(set,g)
print find_intersection(s)

[set([1, 4, 5, 6]), set([0, 2, 3, 7])]

以@Mark 的回答作为基准:

Benchmark with @Mark's answer :

from timeit import timeit


s1="""g=[[], [], [0, 2], [1, 5], [0, 2, 3, 7], [4, 6], [1, 4, 5, 6], [], [], [3, 7]]
sets = [set(i+j) for i in g for j in g if i!=j and (set(i) & set(j))]
    """
s2="""g=[[], [], [0, 2], [1, 5], [0, 2, 3, 7], [4, 6], [1, 4, 5, 6], [], [], [3, 7]]

s=map(set,g)

def find_intersection(m_list):
    for i,v in enumerate(m_list) : 
        for j,k in enumerate(m_list[i+1:],i+1):
           if v & k:
              s[i]=v.union(m_list.pop(j))
              return find_intersection(m_list)
    return m_list 
    """

print ' first: ' ,timeit(stmt=s1, number=100000)
print 'second : ',timeit(stmt=s2, number=100000)

first:  3.8284008503
second :  0.213887929916

相关文章