需要从其成员可能已连接的集合列表中创建集合列表

Question

我在这里实时处理多边形数据，但问题很简单。 我有一个包含数千个多边形索引集（整数）的巨大列表，我需要将该列表尽可能“快速”地简化为一个“连接”索引集列表。 i、 e.任何包含整数的集合也在另一个集合中成为结果中的一个集合。我已经读过一些可能的解决方案，包括集合和图表等。我所要做的只是一个集合的最终列表，这些集合具有任何程度的共性。

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

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=[集合（[0,1,2,3,4,5,6,7,8,9]），集合（[10,11,12,13,14,15]），集合（[16,17,18,19]）]

我也在寻找类似的解决方案，但是得票最多的人在我的大量测试数据中给出了错误的结果。

Merge lists that share common elements

Answer 1

这是工会发现的问题。

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

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

Answer 2

原谅那些乱七八糟的大写字母（自动更正…）：

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