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
Demo :
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])]
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