python - 需要创建一个集合列表，从其成员可能连接的集合列表

Question

我在这里实时处理多边形数据，但问题很简单。我有一个包含数千组多边形索引(整数)的巨大列表，我需要尽可能“快速”地简化列表，将其简化为一组“连接的”索引集。即任何包含也在另一组中的整数的组在结果中成为一个组。我已经阅读了几种可能的解决方案，涉及集合和图形等。我所追求的是具有任何程度共性的集合的最终列表。

我在这里处理大量数据，但为了简单起见，这里有一些示例数据:

setA = set([0,1,2])
setB = set([6,7,8,9])
setC = set([4,5,6])
setD = set([3,4,5,0])
setE = set([10,11,12])
setF = set([11,13,14,15])
setG = set([16,17,18,19])

listOfSets = [setA,setB,setC,setD,setE,setF,setG]

在这种情况下，我正在寻找一个结果如下的列表，尽管排序无关紧要:

connectedFacesListOfSets = [ set([0,1,2,3,4,5,6,7,8,9]), set([10,11,12,13,14,15]), set( [16,17,18,19])]

我一直在寻找类似的解决方案，但得票最高的解决方案在我的大量测试数据上给出了错误的结果。

Merge lists that share common elements

Answer 1

如果没有足够大的集合，很难判断性能，但这里有一些基本代码可以从这里开始:

while True:
    merged_one = False
    supersets = [listOfSets[0]]

    for s in listOfSets[1:]:
        in_super_set = False
        for ss in supersets:
            if s & ss:
               ss |= s
               merged_one = True
               in_super_set = True
               break

        if not in_super_set:
            supersets.append(s)

    print supersets
    if not merged_one:
        break

    listOfSets = supersets       

这对提供的数据进行 3 次迭代。输出如下:

[set([0, 1, 2, 3, 4, 5]), set([4, 5, 6, 7, 8, 9]), set([10, 11, 12, 13, 14, 15]), set([16, 17, 18, 19])]
[set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]), set([10, 11, 12, 13, 14, 15]), set([16, 17, 18, 19])]
[set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]), set([10, 11, 12, 13, 14, 15]), set([16, 17, 18, 19])]