合并具有共同元素的集合？

Question

我想要合并具有共同元素的集合。例如：

input = set([frozenset([1,2,3,4]), frozenset([3,4,5,6,7,8]),  frozenset([1,1000]),
             frozenset([100, 200]), frozenset([100, 300, 400])])

结果：

set([frozenset([1,2,3,4,5,6,7,8, 1000]), frozenset([100,200,300,400])])

有什么高效的方法可以实现这个目标？

- nos

---

@AustinHastings 这个操作使用集合会更快、更容易。我已经发布了一个正确的策略。 - TemporalWolf

@TemporalWolf 这个解决方案涉及到集合，对于列表、元组等都是一样的。你想要将一堆集合合并在一起吗？使用集合。 - aghast

连接组件方法比蛮力法的全对集合并/交算法要高效得多。 - user2357112

这是我的Python代码片段。https://colab.research.google.com/drive/138dsnfmM2mbM7ZJv8fcMKw6bafNyBni1#scrollTo=f3t5qe28Ddd0 - nov05

Answer 1

以下是我尝试过的方法。首先，我做了一些简单但错误的事情。

result = set()
while input:                                                                   
    r = set(input.pop())
    for rr in input.copy():
        if rr & r:                                                  
            input.remove(rr)
            r.update(rr)  
    result.add(frozenset(r))   

这段代码的问题在于合并可能不完整，这取决于input.pop()的顺序。假设input={frozenset([0, 1]), frozenset([2,3]), frozenset([1,2])}，并且按照此分配顺序循环处理三个元素，则results={frozenset([0,1,2]), frozenset([2,3])}。

然后我实现了此帖子中的答案。它首先构建一个新图的邻接列表，每个节点对应于input中的一个frozenset元素。如果两个节点（frozenset）共享相同的元素，则它们之间存在一条边。然后使用深度优先图遍历来查找此新图的连通组件。

result, visited = set(), set()
components = collections.defaultdict(list)
adj_list = collections.defaultdict(list)

def dft(node, key):
    visited.add(node)
    components[key].append(node)
    for neighbor in adj_list[node]:
        if neighbor not in visited:
            dft(neighbor, key)

for r1, r2 in itertools.combinations_with_replacement(input, 2):
    if r1 & r2:
        adj_list[r1].append(r2)
        adj_list[r2].append(r1)
for node in adj_list:
    if node not in visited:
        dft(node, node)

for node, neighbors in components.iteritems():
    result.add(node.union(*neighbors))

- nos

Answer 2

使用内置的set.union() -> 仅包括长度大于0的set.intersection()结果。

---

这个答案从高层次上解释了如何实现你想要的功能。如果你想要一个具体的解决方案，首先你需要展示你尝试解决问题的努力。

- TemporalWolf

---

我没有对你进行投票否决。 - nos

@nos 这并不改变我的政策，即只提供相等的努力 -> 我不介意帮助你找出如何解决它，但你必须展示出解决问题的努力。 - TemporalWolf