Arian Pasquali - 1 year ago 102
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?

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]

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:

if yList and not xList: