需要从可能相连的集合列表创建集合列表

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

我查找过类似的解决方案，但投票最高的那个在我的大测试数据上给出了错误的结果。

合并共享公共元素的列表

Answer 1

抱歉，大小写搞错了（自动纠正功能...）：

# the results cotainer
Connected = set()

sets = # some list of sets

# convert the sets to frozensets (which are hashable and can be added to sets themselves)
Sets = map(frozenset, sets)

for s1 in sets:
    Res = copy.copy(s1)
    For s2 in sets:
        If s1 & s2:
            Res = res | s2
    Connected.add(res)  

Answer 2

这是一个并查集的问题。

虽然我没有用过，但这段Python代码看起来不错。

http://code.activestate.com/recipes/577225-union-find/

Answer 3

没有足够大的数据集，很难判断性能，但这里有一些基础代码可以作为起点：

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