Combine tuples in a list which have the same value

Question

I have a list with tuples like this:

L ={(1,2), (1,4), (1,3), (2,3), (3,4), (3,5), (4,5), (6,7)}

I try to combine these to get equivalence classes (tuples of the same value are merged, like (1,2) and (2,3) becomes (1,2,3)). So you get:

EQ = {(1,2,3,4,5), (6,7)}

What's the easiest way to accomplish this in Python?

Answer 1

You can use the following recursion function . first you can convert the elements to set and go though the set and check any element with the elements after if , when you find an element that have any intersection (v & k) you merg thous set together and remove the second element from list and update the main list :

L ={(1,2), (1,4), (1,3), (2,3), (3,4), (3,5), (4,5), (6,7)}
s=[set(i) for i in L if i]

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 find_intersection(s)

result :

[set([1, 2, 3, 4, 5]), set([6, 7])]
[Finished in 0.0s]

Note that in the second enumerate function i use i+1 for the start number for indexing of m_list[i+1:] because of that the index of k (j) be equal with the index of k in main list.