给定n个元组表示对,返回带有连接元组的列表

Question

给定n个元组,编写一个函数,返回带有连接值的列表.

例:

pairs = [(1,62),
    (1,192),
    (1,168),
    (64,449),
    (263,449),      
    (192,289),
    (128,263),
    (128,345),
    (3,10),
    (10,11)
    ]

结果:

[[1,62,192,168,289],
 [64,449,263,128,345,449],
 [3,10,11]]     

我相信它可以使用图形或树作为数据结构来解决,为每个值创建节点以及每个对的边缘,每个树或图表代表连接值,但我还没有找到解决方案.

在python中生成一个产生这些对的连接值列表的结果的最佳方法是什么？

Answer 1

您可以使用Disjoint Set(Union-Find)实现来解决它.

djs使用所有数字初始化结构.然后为每个元组(x,y)打电话djs.merge(x,y).现在为每个数字x,djs.sameSet(x,)==false为y每个现有集合中的任意一个iff创建一个新集合.

也许这可以帮到你.

Answer 2

您还可以使用networkx作为依赖项。

import networkx as nx

pairs = [(1,62),
        (1,192),
        (1,168),
        (64,449),
        (263,449),      
        (192,289),
        (128,263),
        (128,345),
        (3,10),
        (10,11)]


G = nx.Graph()
G.add_edges_from(pairs)
list(nx.connected_components(G))

Answer 3

我不知道这个问题已经有一个名字了（感谢avim！），所以我继续天真地解决了它。

这个解决方案有点类似于 Eli Rose 的解决方案。不过，我决定发布它，因为它对于大型对列表来说更有效，因为字典lists_by_element会跟踪元素所在的列表，使我们能够避免每次迭代所有列表及其项目是时候我们需要添加一个新项目了。

这是代码：

def connected_tuples(pairs):
    # for every element, we keep a reference to the list it belongs to
    lists_by_element = {}

    def make_new_list_for(x, y):
        lists_by_element[x] = lists_by_element[y] = [x, y]

    def add_element_to_list(lst, el):
        lst.append(el)
        lists_by_element[el] = lst

    def merge_lists(lst1, lst2):
        merged_list = lst1 + lst2
        for el in merged_list:
            lists_by_element[el] = merged_list

    for x, y in pairs:
        xList = lists_by_element.get(x)
        yList = lists_by_element.get(y)

        if not xList and not yList:
            make_new_list_for(x, y)

        if xList and not yList:
            add_element_to_list(xList, y)

        if yList and not xList:
            add_element_to_list(yList, x)            

        if xList and yList and xList != yList:
            merge_lists(xList, yList)

    # return the unique lists present in the dictionary
    return set(tuple(l) for l in lists_by_element.values())

它的工作原理如下： http: //ideone.com/tz9t7m