python - 将列表中所有相交集联合在一起的 pythonic 方法是什么？

Question

我有一个集合列表，

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

我需要将所有相交的部分联合起来，结果如下:

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

执行此操作最优雅的方法是什么？我想不出比 n*n 循环更好的了。

Answer 1

这将产生您描述的输出。它应该比 n * n 运行得更好，除非你没有交叉路口，否则应该有一些好处。

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])]