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

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

你的意思是：

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}])

输出：

[5]

Answer 2

这个问题是关于创建 disjoint sets 的，所以我会使用 union-find 方法。

现在 Python 并不是特别以速度快着称，但是为了展示算法，这里是 DisjointSet class 没有库的实现：

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]]

请注意，我在输入列表中添加了一个空列表，以说明此边界情况保持不变。

注意：有些库提供 union-find/disjoint 设置功能，每个库都略有不同 API，但我想使用其中一个可以提供更好的性能。

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

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

python

arrays

algorithm

performance

intersection