如何编写一个 python3 函数来合并两个集合列表，以便输出列表具有两个输入集中都存在的元素集合？

Question

我有两个集合列表，比方说： [{1, 2, 3}, {4, 5}, {6, 7}] 和 [{1, 2}, {3, 4}, {5, 6, 7}]

列表中没有集合具有相同的元素，并且两个列表中所有集合的总和相同。该函数应检查两个列表中的集合是否具有相同的元素。如果有一些差异，请将它们放在另一组中。

所以上面的例子应该返回：[{1, 2}, {3}, {4}, {5}, {6, 7}]

我处理大型集合，因此我需要此功能尽可能有效。

这是示例代码以及我希望它如何工作：

def mergeSets(x, y):
    out = set()
    for i in x:
        out = out.union(i)
        # this allows me to get the set of all elements but here where my mind stops working
        # the problem sounds simple but thinking hours I can not think of good algorythm for this       issue :(
        # I found set.intersection() function but it works on single sets only, not lists of sets
    return out


x = mergeSets([{1, 2, 3}, {4, 5}, {6, 7}], [{1, 2}, {3, 4}, {5, 6, 7}])
print(x)
# [{1, 2}, {3}, {4}, {5}, {6, 7}]
x = mergeSets([{1, 2}, {3, 4, 5, 6, 7}, {8}], [{1}, {2, 3, 4}, {5, 6, 7, 8}])
print(x)
# [{1}, {2}, {3, 4}, {5, 6, 7}, {8}]

编辑：数据不必排序，甚至可能是与整数不同的类型

EDIT2：输入列表不必排序，因此集合可能以随机顺序出现

Answer 1

鉴于每个值恰好出现在两个集合中（每个输入列表一个），您可以收集每个值的索引对，其中索引对指示该值出现在哪两个集合中（两个列表中的哪些索引处）。

唯一对表示输出中的唯一集，因此此类对的字典可以用于填充结果：

from collections import defaultdict

def merge_sets(lista, listb):
    index_in_a = {
        val: idx
        for idx, elem in enumerate(lista) for val in elem
    }
    set_by_key = defaultdict(set)
    for idx, elem in enumerate(listb):
        for val in elem:
            set_by_key[(index_in_a[val], idx)].add(val)
    return list(set_by_key.values())

这对我来说看起来是 O(n) 。

注意：由于未定义集合上的迭代顺序，因此输出的顺序可能看起来有点混乱，但我假设集合在输出中出现的顺序并不重要。