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)

Solution 1:

You can solve it with Disjoint Set (Union-Find) implementation.

Initialize the structure djs with all of the numbers. Then for each tuple (x,y), call djs.merge(x,y). Now for each number x, create a new set for it iff djs.sameSet(x,)==false for an arbitrary y from each existing set.

Maybe that could help you.

Solution 2:

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:

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

    defmake_new_list_for(x, y):
        lists_by_element[x] = lists_by_element[y] = [x, y]

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

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

        ifnot xList andnot yList:
            make_new_list_for(x, y)

        if xList andnot yList:
            add_element_to_list(xList, y)

        if yList andnot 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 dictionaryreturnset(tuple(l) for l in lists_by_element.values())

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

Solution 3:

You also could use networkx as a dependency.

import networkx as nxpairs= [(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))

Solution 4:

Another solution that is more compact than wOlf's but handles merge contrary to Eli's:

defconnected_components(pairs):
    components = []
    for a, b in pairs:
        for component in components:
            if a in component:
                for i, other_component inenumerate(components):
                    if b in other_component and other_component != component: # a, and b are already in different components: merge
                        component.extend(other_component)
                        components[i:i+1] = []
                        break# we don't have to look for other components for belse: # b wasn't found in any other componentif b notin component:
                        component.append(b)
                break# we don't have to look for other components for aif b in component: # a wasn't in in the component 
                component.append(a)
                break# we don't have to look furtherelse: # neither a nor b were found
            components.append([a, b])
    return components

Notice that I rely on breaking out of loops when I find an element in a component so that I can use the else clause of the loop to handle the case where the elements are not yet in any component (the else is executed if the loop ended without break).

Solution 5:

I came up with 2 different solutions:

The first one I prefer is about linking each record with a parent. And then of course navigate further in the hierarchy until an element is mapped to itself.

---

So the code would be:

defbuild_mapping(input_pairs):
    mapping = {}

    for pair in input_pairs:
        left = pair[0]
        right = pair[1]

        parent_left = Noneif left notin mapping else mapping[left]
        parent_right = Noneif right notin mapping else mapping[right]

        if parent_left isNoneand parent_right isNone:
            mapping[left] = left
            mapping[right] = left

            continueif parent_left isnotNoneand parent_right isnotNone:
            if parent_left == parent_right:
                continue

            top_left_parent = mapping[parent_left]
            top_right_parent = mapping[parent_right]
            while top_left_parent != mapping[top_left_parent]:
                mapping[left] = top_left_parent
                top_left_parent = mapping[top_left_parent]

            mapping[top_left_parent] = top_right_parent
            mapping[left] = top_right_parent

            continueif parent_left isNone:
            mapping[left] = parent_right
        else:
            mapping[right] = parent_left

    return mapping


defget_groups(input_pairs):
    mapping = build_mapping(input_pairs)

    groups = {}
    for elt, parent in mapping.items():
        if parent notin groups:
            groups[parent] = set()

        groups[parent].add(elt)

    returnlist(groups.values())

So, with the following input:

groups = get_groups([('A', 'B'), ('A', 'C'), ('D', 'A'), ('E', 'F'), 
                     ('F', 'C'), ('G', 'H'), ('I', 'J'), ('K', 'L'), 
                     ('L', 'M'), ('M', 'N')])

We get:

[{'A', 'B', 'C', 'D', 'E', 'F'}, {'G', 'H'}, {'I', 'J'}, {'K', 'L', 'M', 'N'}]

---

The second maybe less efficient solution would be:

defget_groups_second_method(input_pairs):
    groups = []

    for pair in input_pairs:
        left = pair[0]
        right = pair[1]

        left_group = None
        right_group = Nonefor i inrange(0, len(groups)):
            group = groups[i]

            if left in group:
                left_group = (group, i)

            if right in group:
                right_group = (group, i)

        if left_group isnotNoneand right_group isnotNone:
            merged = right_group[0].union(left_group[0])
            groups[right_group[1]] = merged
            groups.pop(left_group[1])
            continueif left_group isNoneand right_group isNone:
            new_group = {left, right}
            groups.append(new_group)
            continueif left_group isNone:
            right_group[0].add(left)
        else:
            left_group[0].add(right)

    return groups