首页 文章

列表中的元组交集 - python

提问于
浏览
2

我有一个像这样的元组列表:

all_tuples=[(92, 242),(355, 403),(355, 436),(355, 489),(403, 436),(436, 489),(515, 517),(517, 859),(634, 775),(701, 859),(775, 859)]

我需要采取所有元组的交集并将它们联合起来 .

The desired result = [{92, 242},{355, 403,436,489},{515, 517,859,701,775,634}]

那就是交叉的元组是迭代的联合 .

我试图将元组转换为集合,然后采取交集,但没有工作 . 任何的想法?

3 回答

  • 0

    此解决方案构建了一个等价类列表,其中在同一元组中是我们的等价关系 . 对于每个元组,我们列出列表中与该元组的某些元素匹配的所有集合 . 如果没有,我们创建一组该元组并将其添加到列表中 . 如果有,我们更新该集以包括元组的其他项 . 如果有多个,我们将它们从列表中删除,将它们和元组组合到一个集合,然后将该集合添加到列表中 .

    res = []
    for t in all_tuples:
        matched = []
        for s in res:
            if s.intersection(t):
                matched.append(s)
        if not matched:
            res.append(set(t))
        elif len(matched) == 1:
            matched[0].update(t)
        else:
            res = [subl for subl in res if subl not in matched]
            res.append(set.union(*matched, t))
    
    print(res)
    # [{242, 92}, {489, 436, 355, 403}, {515, 517, 775, 634, 859, 701}]
    
  • 1

    这是网络问题,使用 networkx

    import networkx as nx 
    G=nx.Graph()
    all_tuples=[(92, 242),(355, 403),(355, 436),(355, 489),(403, 436),(436, 489),(515, 517),(517, 859),(634, 775),(701, 859),(775, 859)]
    G.add_edges_from(all_tuples)
    list(nx.connected_components(G))
    Out[1216]: [{92, 242}, {355, 403, 436, 489}, {515, 517, 634, 701, 775, 859}]
    
  • 8

    只是为什么不,这里是一个只有列表和元组的实现 .

    all_tuples=[(92, 242),(355, 403),(355, 436),(355, 489),(403, 436),(436, 489),(515, 517),(517, 859),(634, 775),(701, 859),(775, 859)]
    
    curr_min, curr_max = all_tuples[0]
    final = []
    intermediate = [curr_min, curr_max]
    for next_left, next_right in all_tuples[1:]:
        if curr_max >= next_left:
            intermediate.extend([next_left, next_right])
            curr_min, curr_max = min(curr_min, next_left), max(curr_max, next_right)
        else:
            final.append(set(intermediate))
            intermediate = []
            curr_min, curr_max = next_left, next_right
    final.append(set(intermediate))
    

相关问题