给定n个表示对的元组，返回带有连接的元组的列表 [英] Given n tuples representing pairs, return a list with connected tuples

问题描述

给出n个元组，编写一个函数，该函数将返回具有连接值的列表。

Given n tuples, write a function that will return a list with connected values.

示例：

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

我相信可以使用图或树作为数据结构，为每个值创建节点，并为每对边创建边，每个树或图代表连接的值，但我没有找到

I believe it could be solved using graphs or trees as data structure, creating nodes for each value and and edges for each pair with each tree or graph representing connected values, but I didn't find a solution yet.

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

What would be the best way to produce in python a result that yields a list of connected values for those pairs?

推荐答案

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

I didn't know this problem already had a name (thanks avim!), so I went ahead and solved it naively.

此解决方案与Eli Rose的解决方案有些相似。我决定发布它，因为对于大型的成对列表，由于 lists_by_element 词典跟踪元素所在列表的事实，它的效率更高。 ，这样我们就可以避免每次需要添加新项目时都遍历所有列表及其项目。

This solution is somewhat similar to Eli Rose's. I decided to post it though, because it is a bit more efficient for large lists of pairs, due to the fact that the lists_by_element dictionary keeps track of the list an element is in, allowing us to avoid iterating through all the lists and their items every time we need to add a new item.

这里是代码：

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

这篇关于给定n个表示对的元组，返回带有连接的元组的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！