What's the pythonic way to unite all the 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 unite all those that are intersecting, so that the result is the following:

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

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

See [this question](http://stackoverflow.com/questions/9110837/python-simple-list-merging-based-on-intersections). — DSM, Mar 14 '12 at 20:05

score 4 · Accepted Answer · answered Mar 14 '12 at 20:09

This would produce the output you describe. It should run better than n * n unless you have no intersections, but otherwise 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])]

score 1 · Answer 2 · answered Mar 14 '12 at 20:11

I'd 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 will be O(n*n) in the worst case (no sets intersect).

What's the pythonic way to unite all the intersecting sets in a list?

2 Answers2