Python merge multiple list with intersection

Question

Possible Duplicate:
Python: simple list merging based on intersections

I have a multiple list:

 list=[[1,2,3],[3,5,6],[8,9,10],[11,12,13]]

Is there a smart and fast way to get all the sublists with at least one intersection. In my example I want that the code return

 result=[[1,2,3,5,6],[8,9,10],[11,12,13]]

Answer 1

This works, but maybe isn't very elegant:

def merge_lists(l):
        s=map(set, l)
        i, n=0, len(s)
        while i < n-1:
                for j in xrange(i+1, n):
                        if s[i].intersection(s[j]):
                                s[i].update(s[j])
                                del s[j]
                                n-=1
                                break
                else:
                        i+=1
        return [sorted(i) for i in s]

Answer 2

You can do this with essentially a single pass through the data:

list_of_lists = [[1, 2, 3], [3, 5, 6], [8, 9, 10], [11, 12, 13]]
sets = {}
for lst in list_of_lists:
    s = set(lst)
    t = set()
    for x in s:
        if x in sets:
            t.update(sets[x])
        else:
            sets[x] = s
    for y in t:
        sets[y] = s
    s.update(t)
ids = set()
for s in sets.itervalues():
    if id(s) not in ids:
        ids.add(id(s))
        print s

This creates a dictionary sets mapping each element to the set it belongs to. If some element has been seen before, its set is subsumed into the current one and all dictinary entries mapping to the former set are updated.

Finally we need to find all unique sets in the values of the dictionary sets. Note that while I implemented this as a dictionary of sets, the code also works with lists instead of sets.

Answer 3

Nice question! It's much simpler if you think of it as a connected-components problem in a graph. The following code uses the excellent networkx graph library and the pairs function from this question.

def pairs(lst):
    i = iter(lst)
    first = prev = item = i.next()
    for item in i:
        yield prev, item
        prev = item
    yield item, first

lists = [[1,2,3],[3,5,6],[8,9,10],[11,12,13]]

import networkx
g = networkx.Graph()
for sub_list in lists:
    for edge in pairs(sub_list):
            g.add_edge(*edge)

networkx.connected_components(g)
[[1, 2, 3, 5, 6], [8, 9, 10], [11, 12, 13]]

---

Explanation

We create a new (empty) graph g. For each sub-list in lists, consider its elements as nodes of the graph and add an edge between them. (Since we only care about connectedness, we don't need to add all the edges -- only adjacent ones!) Note that add_edge takes two objects, treats them as nodes (and adds them if they aren't already there), and adds an edge between them.

Then, we just find the connected components of the graph -- a solved problem! -- and output them as our intersecting sets.