如何仅递归地加入具有共同元素的集合，同时保留所有其他集合不变？

Question

假设我有一个定义如下的集合列表

set_list = [{1, 2}, {2, 3}, {3, 50, 60}, {70, 90}, {70, 80}, {1, 2}, {999, 888}]

我想定义一个函数，该函数接收如上所述的集合列表并输出一个新的集合列表，这样如果上面的列表作为参数传递，则输出将如下 我该

output = [{1, 2, 3, 50, 60}, {70, 80, 90}, {999, 888}]

如何实施这样的事情？

请注意，我使用列表是为了方便（我不关心集合的顺序，但我确实希望输出不包含重复项），因为集合不能是集合的元素。我知道可以用frozensets，但是写起来很麻烦。尽管如此，任何使用 freezesets 或其他方式的实现都会很棒。

Answer 1

由于您需要递归解决方案，因此这里有一个使用 frozensets 的递归解决方案 -

set_list = [{1, 2}, {2, 3}, {3, 50, 60}, {70, 90}, {70, 80}, {1, 2}, {999, 888}]
input_list = set(frozenset(x) for x in set_list)

def merge(data):
    for x in set(data):
        for y in set(data):
            if x == y:
                continue
            if not x.isdisjoint(y):
                data.remove(x)
                data.remove(y)
                data.add(x.union(y))
                return merge(data)
    return data

print(merge(input_list))

输出 -

{frozenset({888, 999}), frozenset({80, 90, 70}), frozenset({1, 50, 3, 2, 60})}

---

例如，set_list 中的一个集合与 output 中的多个集合匹配代码> -

set_list = [{1, 2}, {2, 3}, {3, 50, 60}, {70, 90}, {70, 80}, {1, 2}, {999, 888}, {888, 2}]

输出 -

{frozenset({1, 2, 3, 50, 999, 888, 60}), frozenset({80, 90, 70})}

Answer 2

我不确定这是否是最好的方法，但可能会有所帮助。

set_list = [{1, 2}, {2, 3}, {3, 50, 60}, {70, 90}, {70, 80}, {1, 2}, {999, 888}]

result = [set_list[0]]
for elem in set_list:
    if not elem.isdisjoint(result[-1]):
        result[-1].update(elem)
    else:
        _updated = False
        for i, set_ in enumerate(result):
            if not elem.isdisjoint(set_):
                result[i].update(elem)
                _updated = True
        if not _updated:
            result.append(elem)

print(result)

输出：

[{1, 2, 3, 50, 60}, {80, 90, 70}, {888, 999}]

编辑：
正如 Max Miller 指出的那样，这对于某些输入不起作用，他的解决方案更加完整。