Fastest method to update all list entries with union of all intersecting entries

user_3238875 0
Viewed 142

I am looking for a fast method to traverse a list of sets, and to expand each set by finding its union with any other element of the list with which it shares at least one element.

For example, suppose that I have four rows of data, where each row corresponds to a set of unique elements

0, 5, 101
8, 9, 19, 21
78, 79
5, 7, 63, 64

The first and the last rows have the intersecting element 5 and so after performing my operation I want to have the unions

0, 5, 7, 63, 64, 101
8, 9, 19, 21
78, 79
0, 5, 7, 63, 64, 101

Right now, I can nearly do this with two loops:

def consolidate_list(arr):
    """
    arr (list) : A list of lists, where the inner lists correspond to sets of unique integers
    """
    arr_out = list()
    for item1 in arr:
        item_additional = list() # a list containing all overlapping elements
        for item2 in arr:
            if len(np.intersect1d(item1, item2)) > 0:
                item_additional.append(np.copy(item2))
        out_val = np.unique(np.hstack([np.copy(item1)] + item_additional)) # find union of all lists

        arr_out.append(out_val)
        
return arr_out

The issue with this approach is that it needs to be run multiple times, until the output stops changing. Since the input might be jagged (ie, different numbers of elements per set), I can't see a way to vectorize this function.

intersection arrays algorithm python performance
2 Answers

This problem is about creating disjoint sets and so I would use union-find methods.

Now Python is not particularly known for being fast, but for the sake of showing the algorithm, here is an implementation of a DisjointSet class without libraries:

class DisjointSet:
    class Element:
        def __init__(self):
            self.parent = self
            self.rank = 0


    def __init__(self):
        self.elements = {}

    def find(self, key):
        el = self.elements.get(key, None)
        if not el:
            el = self.Element()
            self.elements[key] = el
        else: # Path splitting algorithm
            while el.parent != el:
                el, el.parent = el.parent, el.parent.parent
        return el

    def union(self, key=None, *otherkeys):
        if key is not None:
            root = self.find(key)
            for otherkey in otherkeys:
                el = self.find(otherkey)
                if el != root:
                    # Union by rank
                    if root.rank < el.rank:
                        root, el = el, root
                    el.parent = root
                    if root.rank == el.rank:
                        root.rank += 1

    def groups(self):
        result = { el: [] for el in self.elements.values() 
                          if el.parent == el }
        for key in self.elements:
            result[self.find(key)].append(key)
        return result

Here is how you could use it for this particular problem:

def solve(lists):
    disjoint = DisjointSet()
    for lst in lists:
        disjoint.union(*lst)
            
    groups = disjoint.groups()
    return [lst and groups[disjoint.find(lst[0])] for lst in lists]

Example call:

data = [
    [0, 5, 101],
    [8, 9, 19, 21],
    [],
    [78, 79],
    [5, 7, 63, 64]
]
result = solve(data)

The result will be:

[[0, 5, 101, 7, 63, 64], [8, 9, 19, 21], [], [78, 79], [0, 5, 101, 7, 63, 64]]

Note that I added an empty list in the input list, so to illustrate that this boundary case remains unaltered.

NB: There are libraries out there that provide union-find/disjoint set functionality, each with a slightly different API, but I suppose that using one of those can give a better performance.

user_54598390

Do you mean by?:

from itertools import combinations
l1 = [0, 5, 7, 63, 64, 101]
l2 = [8, 9, 19]
l3 = [78, 79]
l4 = [5, 4, 34]
print([v for x, y in combinations([l1, l2, l3, l4], 2) for v in {*x} & {*y}])

Output:

[5]
user_87083640
Related