python - 用所有相交条目的并集更新所有列表条目的最快方法

Question

我正在寻找一种快速方法来遍历集合列表，并通过找到它与列表中至少共享一个元素的任何其他元素的并集来扩展每个集合。
例如，假设我有四行数据，其中每一行对应一组唯一的元素

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

第一行和最后一行有相交元素 5，所以在执行我的操作后我想要联合

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

现在，我几乎可以用两个循环来做到这一点:

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

这种方法的问题在于它需要运行多次，直到输出停止变化。由于输入可能是锯齿状的(即，每组的元素数量不同)，我看不到矢量化此函数的方法。

Answer 1

这个问题是关于创建disjoint sets所以我会使用 union-find 方法。
现在 Python 并不是特别出名，但为了展示算法，这里是一个 DisjointSet 的实现。没有库的类:

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

以下是您如何将其用于此特定问题:

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]

示例调用:

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

结果将是:

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

请注意，我在输入列表中添加了一个空列表，以便说明此边界情况保持不变。
注意:有一些库提供联合查找/不相交集功能，每个库的 API 略有不同，但我认为使用其中之一可以提供更好的性能。