Find sets of disjoint sets from a list of tuples or sets in python -

here problem: have list of tuples (could sets if needed). instance:

a = [(1, 5), (4, 2), (4, 3), (5, 4), (6, 3), (7, 6)] 

what want find list

r = [(1, 5, 4, 2, 3, 6, 7)] 

because intersection not empty once sets put together.

for example

a = [(1, 5), (4, 2), (4, 3), (5, 4), (6, 3), (7, 6), (8, 9)] 

the result should be

r = [(1, 5, 4, 2, 3, 6, 7), (8, 9)] 

hope problem clear. elegant way in python, if any?

cheers

an interesting problem!

here's attempt, i'm sure it's not efficient way

a = [(1, 5), (4, 2), (4, 3), (5, 4), (6, 3), (7, 6), (8, 9)] # = [(1, 5), (4, 2), (4, 3), (5, 4), (6, 3), (7, 6)]  d = {tuple(t): set(t) t in a}  # forces keys unique  while true:     tuple_, set1 in d.items():         try:             match = next(k k, set2 in d.iteritems() if k != tuple_ , set1 & set2)         except stopiteration:             # no match key - keep looking             continue         else:             print 'merging', tuple(set1), match             d[tuple_] = set1 | d.pop(match)             break     else:         # no match key - done!         break  output = sorted(tuple(s) s in d.itervalues()) print output 

the output this:

merging (4, 5) (1, 5) merging (1, 4, 5) (4, 3) merging (1, 3, 4, 5) (6, 3) merging (1, 3, 4, 5, 6) (7, 6) merging (1, 3, 4, 5, 6, 7) (4, 2) [(1, 2, 3, 4, 5, 6, 7), (8, 9)]