如何合并具有交集的集合（连通组件算法）？

Question

有没有有效的方法可以合并具有交集的集合。例如：

l = [{1, 3}, {2, 3}, {4, 5}, {6, 5}, {7, 5}, {8, 9}]

期望的结果是：

r = [{1, 2, 3}, {4, 5, 6, 7}, {8, 9}]

所有有交集（共同组件）的集合应该被合并。例如：

{1, 3} & {2, 3}
# {3}

所以这两个集合应该合并：

{1, 3} | {2, 3}
# {1, 2, 3}

很遗憾，我没有任何可行的解决方案。

更新：结果中集合的顺序不重要。

- Mykola Zotko

---

请指定合并的条件是什么？ - han solo

看起来你需要一个连通分量算法。 - mkrieger1

为避免投机性回答，请解释您想要实现的具体目标，并展示您已经尝试过什么以及问题所在。 - mkrieger1

像 [{1,2}, {2,3}, {3,4}] 这样的输入，期望的输出是什么？是 [{1,2,3,4}] 吗？还是 [{1,2,3}, {3,4}]？ - Aran-Fey

@mkrieger1 结果必须是 {1, 2, 3, 4}。 - Mykola Zotko

Answer 1

一种高效实现 连通分量算法 的方法，正如评论中 @mkrieger1 所提到的，是将列表转换成可哈希化的 frozensets 集合。这样当您遍历它并发现一个与当前集合相交的 frozenset 时，您可以轻松地从池中删除它：

pool = set(map(frozenset, l))
groups = []
while pool:
    groups.append(set(pool.pop()))
    while True:
        for candidate in pool:
            if groups[-1] & candidate:
                groups[-1] |= candidate
                pool.remove(candidate)
                break
        else:
            break

假设 l = [{1, 3}, {2, 3}, {4, 5}, {6, 5}, {7, 5}, {8, 9}]，groups 将变为：

[{1, 2, 3}, {4, 5, 6, 7}, {8, 9}]

假设 l = [{1, 2}, {3, 4}, {2, 3}]，那么 groups 将变成：

[{1, 2, 3, 4}]

假设 l = [{1}, {2}, {1, 2}]，则 groups 将变为：

[{1, 2}]

- blhsing

---

这是一个预期结果还是一个错误 [{1}, {2}, {1, 2}]:[{1, 2}, {1}] - Benoît P

确实是个bug。我用一个while循环修复了它。谢谢。 - blhsing

Answer 2

我提出这个解决方案：

def merge_sets(set_list):
    if len(set_list) == 0:
        # short circuit to avoid errors
        return []

    current_set = set_list[0]
    new_set_list = [current_set, ]

    for s in set_list[1:]:          # iterate from the second element
        if len(current_set.intersection(s)) > 0:
            current_set.update(s)
        else:
            current_set = set(s)    # copy
            new_set_list.append(current_set)

    return new_set_list

适用于以下测试用例：

test_cases = [
    {
        'input': [{1, 3}, {2, 3}, {4, 5}, {6, 5}, {7, 5}, {8, 9}],
        'output': [{1, 2, 3}, {4, 5, 6, 7}, {8, 9}],
    },
    {
        'input': [{1, 2}, {2, 3}, {3, 4}],
        'output': [{1, 2, 3, 4}, ],
    },
    {
        'input': [{1}, {2}, {1, 2}],
        'output': [{1}, {1, 2}],
    },
    {
        'input': [{1, 2}, {3, 4}, {2, 3}],
        'output': [{1, 2}, {2, 3, 4}],
    },
]

for case in test_cases:
    print('input   ', case['input'])
    print('expected', case['output'])

    new_output = merge_sets(case['input'])
    print('real    ', new_output)
    assert new_output == case['output']

这对你有用吗？

- Ralf

---

[{1}, {1, 2}] 存在交集，因此输出结果是错误的。 - Benoît P

注意：我的解决方案考虑了输入列表中集合的顺序。这符合@MykolaZotko的需求吗？或者输入可以是无序的一组集合，需要将它们合并，直到没有更多可合并的为止？ - Ralf

@BenoîtPilatte 这个算法是否应该考虑输入集的顺序？如果是的话，那么我的解决方案可以运行；如果不是，那么我的解决方案就不正确。 - Ralf

对于 [{1}, {2}, {1,2}] ，结果必须是 {1, 2} 而不是 {1}, {1, 2}。 - Benoît P

@BenoîtPilatte 顺序不重要。 - Mykola Zotko