Arian Pasquali Arian Pasquali - 21 days ago 6
Python Question

Given n tuples representing pairs, return a list with connected tuples

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

Example:

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


result:

[[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.

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

Answer

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

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.

Here's the code:

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

And here's how it works: http://ideone.com/tz9t7m