合并非空交集集的最简单方法

Question

我有一个集合列表，mergeList，我使用下面的代码在mergeList中合并那些具有非空交集的集合。但是它不会合并所有有交集的集合，也就是说，在while循环之后，列表中仍然有一些集合有交集。在

mergeList = [set([0.5]), set([1.5]), set([2.5]), set([3.5]), set([4.5]), set([5.5]), set([2.5, 6.5]), set([6.5]), set([1.5, 7.5]), set([7.5]), set([8.5]), set([0.5, 9.5]), set([9.5]), set([10.5]), set([11.5]), set([12.5]), set([13.5]), set([2.5, 14.5]), set([14.5]), set([8.5, 15.5]), set([15.5]), set([16.5]), set([15.5, 17.5]), set([13.5, 17.5]), set([17.5]), set([8.5, 18.5]), set([18.5]), set([11.5, 19.5]), set([19.5]), set([4.5, 20.5]), set([10.5, 20.5]), set([20.5]), set([8.5, 21.5]), set([21.5]), set([3.5, 22.5]), set([8.5, 22.5]), set([22.5]), set([11.5, 23.5]), set([23.5]), set([12.5, 24.5]), set([24.5]), set([19.5, 25.5]), set([25.5]), set([12.5, 26.5]), set([26.5]), set([27.5]), set([0.5, 28.5]), set([9.5, 28.5]), set([28.5]), set([11.5, 29.5]), set([23.5, 29.5]), set([29.5]), set([5.5, 30.5]), set([30.5]), set([5.5, 31.5]), set([31.5]), set([2.5, 32.5]), set([32.5]), set([16.5, 33.5]), set([33.5]), set([2.5, 34.5]), set([34.5]), set([2.5, 35.5]), set([16.5, 35.5]), set([35.5]), set([12.5, 36.5]), set([9.5, 36.5]), set([36.5]), set([11.5, 37.5]), set([19.5, 37.5]), set([27.5, 37.5]), set([37.5]), set([38.5]), set([39.5]), set([34.5, 40.5]), set([2.5, 40.5]), set([40.5]), set([29.5, 41.5]), set([41.5]), set([13.5, 42.5]), set([17.5, 42.5]), set([42.5]), set([4.5, 43.5]), set([43.5]), set([5.5, 44.5]), set([44.5]), set([43.5, 45.5]), set([45.5]), set([36.5, 46.5]), set([46.5]), set([19.5, 47.5]), set([47.5]), set([13.5, 48.5]), set([48.5]), set([11.5, 49.5]), set([29.5, 49.5]), set([49.5]), set([9.5, 50.5]), set([50.5]), set([30.5, 51.5]), set([1.5, 51.5]), set([51.5]), set([35.5, 52.5]), set([2.5, 52.5]), set([6.5, 52.5]), set([16.5, 52.5]), set([52.5]), set([53.5]), set([43.5, 54.5]), set([4.5, 54.5]), set([54.5]), set([2.5, 55.5]), set([55.5]), set([1.5, 56.5]), set([56.5]), set([8.5, 57.5]), set([57.5]), set([38.5, 58.5]), set([58.5]), set([13.5, 59.5]), set([48.5, 59.5]), set([59.5]), set([10.5, 60.5]), set([20.5, 60.5]), set([60.5]), set([61.5]), set([9.5, 62.5]), set([62.5]), set([47.5, 63.5]), set([25.5, 63.5]), set([63.5]), set([0.5, 64.5]), set([64.5]), set([46.5, 65.5]), set([65.5]), set([16.5, 66.5]), set([35.5, 66.5]), set([66.5]), set([15.5, 67.5]), set([17.5, 67.5]), set([67.5]), set([16.5, 68.5]), set([68.5]), set([53.5, 69.5]), set([69.5]), set([0.5, 70.5]), set([70.5]), set([51.5, 71.5]), set([1.5, 71.5]), set([71.5]), set([70.5, 72.5]), set([0.5, 72.5]), set([72.5]), set([69.5, 73.5]), set([73.5]), set([1.5, 74.5]), set([56.5, 74.5]), set([74.5]), set([10.5, 75.5]), set([75.5]), set([14.5, 76.5]), set([2.5, 76.5]), set([76.5]), set([19.5, 77.5]), set([77.5]), set([2.5, 78.5]), set([58.5, 78.5]), set([40.5, 78.5]), set([78.5]), set([0.5, 79.5]), set([72.5, 79.5]), set([79.5]), set([39.5, 80.5]), set([80.5]), set([29.5, 81.5]), set([41.5, 81.5]), set([81.5]), set([19.5, 82.5]), set([82.5]), set([37.5, 83.5]), set([11.5, 83.5]), set([19.5, 83.5]), set([83.5]), set([11.5, 84.5]), set([84.5]), set([27.5, 85.5]), set([45.5, 85.5]), set([85.5]), set([64.5, 86.5]), set([0.5, 86.5]), set([86.5]), set([65.5, 87.5]), set([9.5, 87.5]), set([46.5, 87.5]), set([36.5, 87.5]), set([87.5]), set([38.5, 88.5]), set([88.5]), set([34.5, 89.5]), set([58.5, 89.5]), set([89.5]), set([4.5, 90.5]), set([90.5]), set([12.5, 91.5]), set([26.5, 91.5]), set([91.5]), set([64.5, 92.5]), set([92.5]), set([3.5, 93.5]), set([22.5, 93.5]), set([8.5, 93.5]), set([93.5]), set([0.5, 94.5]), set([94.5]), set([48.5, 95.5]), set([42.5, 95.5]), set([13.5, 95.5]), set([95.5]), set([19.5, 96.5]), set([96.5]), set([12.5, 97.5]), set([91.5, 97.5]), set([97.5]), set([20.5, 98.5]), set([4.5, 98.5]), set([98.5]), set([8.5, 99.5]), set([99.5]), set([16.5, 100.5]), set([66.5, 100.5]), set([100.5])]

while i < len(mergeList):
    for j in range(len(mergeList) - 1, i, -1):
        if not mergeList[i].isdisjoint(mergeList[j]):
            mergeList[i] = mergeList[i].union(mergeList[j])
            del mergeList[j]

你知道这里有什么问题吗？在

更新：我为示例添加了一些数据，我希望这不会使问题变得复杂。在

Answer 1

既然我明白了这个问题。问题是，可能还有其他后续值需要合并到第i个条目中。因此，您必须重复，直到没有更改为止。在

示例：

{1}{2}{23}

OP的算法将{1}与{2}->；{1，2}{2，3}合并。在

在这一步之后，它将设置i=1，不再查看{1，2}集。在

i = 0
while i < len(mergeList):
    changes = True
    while changes:
        changes = False
        for j in range(len(mergeList) - 1, i, -1):
            if not mergeList[i].isdisjoint(mergeList[j]):
                changes = True
                mergeList[i] |= mergeList[j]
                del mergeList[j]
    i += 1

Answer 2

如果我把问题简单化了，请告诉我，但你不能这样做吗？在

reduce(lambda a,b: a|b, mergeList)

在这里，我们定义了一个lambda函数来联合集合（它删除了相交中的重复项）。将它放在reduce函数中会将其应用于累积集a和列表b中的每个附加集。在

Answer 3

问题的出现是因为两个集合在检查它们是否相交之前可能不会开始相交。在

{{cd2}和^{cd2}相交。你做下面的事。在

1. 检查A和{}是否相交。没有十字路口。在
2. 检查A和{}是否相交。它们相交，因此您将A替换为A.union(C)，并删除{}。现在A与B相交，C不见了。在
3. 你完成了A。接着看B，但是没有什么可以与之相比的了。你停下来。在

简单而快速的解决方法是不断检查一个集合与其他集合的交集，直到你通过所有其他集合而没有找到任何交集为止。在