python - merge lists with intersection

Question

Given that:

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

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

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.

Answer 1

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