What is the pythonic way to combine all intersecting sets in a list?

Question

I have a list of sets,

[set([0, 1, 2]), set([3, 2]), set([4, 1]), set([5, 6]), set([7, 8])] 

and I need to combine all intersecting so that the result is as follows:

 [set([0, 1, 2, 3, 4]), set([5, 6]), set([7, 8])] 

What is the most elegant way to do this? I can't think of anything better than an n * n loop.

Answer 1

This will produce the result you are describing. It should work better than n * n if you don't have intersections, but otherwise it should benefit some.

 mysets = [set([0, 1, 2]), set([3, 2]), set([4, 1]), set([5, 6]), set([7, 8])] # Require at least one set in the output. output = [mysets.pop(0)] while mysets: test = mysets.pop(0) for idx, other in enumerate(output): if test & other: output[idx] |= test break else: output.append(test) # output -> [set([0, 1, 2, 3, 4]), set([5, 6]), set([8, 7])] 

Answer 2

I would do something like this:

 sets = [set([0, 1, 2]), set([3, 2]), set([4, 1]), set([5, 6]), set([7, 8])] intersections = [sets[0]] for start_set in sets[1:]: intersects = False for final_set in intersections: if len(final_set & start_set) > 0: final_set.update(start_set) intersects = True if not intersects: intersections.append(start_set) 

It should be O (n) in the best case (all sets intersect), but it will be O (n * n) in the worst case (no sets intersect).