pythonlistloopstransitive-closure

Create a list of unique numbers by applying transitive closure

I have a list of tuples (each tuple consists of 2 numbers) like:

array = [(1, 2), (1, 3), (2, 4), (5, 8), (8, 10)]

Lets say, these numbers are ids of some db objects (records) and inside a tuple, there are ids of duplicate objects. Which means 1 and 2 are duplicate. 1 and 3 are duplicate which means 2 and 3 are also duplicate.

if a == b and b == c then a == c

Now I want to merge all these duplicate objects ids into a single tuple like this:

output = [(1, 2, 3, 4), (5, 8, 10)]

I know I can do this using loops and redundant matches. I just want some better solution with low processing / calculations (if there is any).

Solution

  • I think the most efficient way to achieve this will be using set as:

    def transitive_cloure(array):
    new_list = [set(array.pop(0))]  # initialize first set with value of index `0`

    for item in array:
        for i, s in enumerate(new_list):
            if any(x in s for x in item):
                new_list[i] = new_list[i].union(item)
                break
        else:
            new_list.append(set(item))
    return new_list

    Sample run:

    >>> transitive_cloure([(1,2), (1,3), (2,4), (5,8), (8,10)])
[{1, 2, 3, 4}, {8, 10, 5}]

    Comparison with other answers (on Python 3.4):