如何以递归方式仅加入它们之间具有共同元素的集合，同时将所有其他集合保持原样？

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，但是写起来很麻烦。尽管如此，任何使用 frozensets 或其他方式的实现都会很棒。

Answer 1

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

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 指出的那样，这对某些输入不起作用，他的解决方案更完整。

Answer 2

既然你想要一个递归的解决方案，这里有一个使用 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})}

如何以递归方式仅加入它们之间具有共同元素的集合，同时将所有其他集合保持原样？

How do I join only sets that have common elements between them recursively while leaving all others sets as is?

python

set