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

我想用普通元素合并集合。例如合并具有共同元素的集合？

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])])

什么将是一个有效的方式来实现这一目标？

来源

2017-02-13 nos

@AustinHastings这个操作更快，更容易设置。我已经发布了一个适当的策略。 – TemporalWolf

@TemporalWolf解决方案涉及到集合，并且对于列表，元组等等也是一样的。你想将一堆集合合并在一起？内置套件。 –

连接组件方法比蛮力全双对'set.union' /'set.intersection'算法效率更高。 – user2357112

这是我试过的。首先，我做了一些简单而错误

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])}。

然后我执行了答案in this post。它首先建立一个新图的邻接列表，每个节点对应于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))

来源

2017-02-18 02:41:01 nos

使用内置set.union() - >只包括结果，其中的set.intersection()长度大于0

这个答案说明了在较高的水平如何实现你想要什么。如果你想要一个特定的解决方案，你必须首先显示你的努力来解决问题。

来源

2017-02-13 19:30:36 TemporalWolf

我没有投票给你。 – nos

@nos这并不会改变我的政策，只会提供同等的努力 - >我不介意帮助你弄清楚如何去做，但你必须努力解决它。 – TemporalWolf

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

回答

相关问题