一种在集合中寻找集对的有效方法

Question

我有一组集合：{1，2，3.}，我想找到所有的对(，)，比如∩≠∅。

我唯一能想到的方法就是重复条件检查Σ时间。

如果我可以用python-ish伪代码来表示这一点：

from copy import deepcopy

setA = {A1, A2, A3, A4....}
setACopy = deepcopy(setA)

intersectingPairs = set()

for Ai in setA:
    for Aj in setACopy:
        if isIntersect(Ai, Aj):
            intersectingPairs.add((Ai, Aj))
    setACopy.remove(Ai)

随着setA大小的增加，我希望这是非常耗时的。

是否有更好的算法可供参考？

Answer 1

您可以通过线性解析数据来构建查找表，而不是单独检查每一对。如果连接是稀疏的，这会很快产生您想要的唯一对。

from itertools import combinations
from collections import defaultdict
from pprint import pprint

A1 = {1, 2, 3}
A2 = {2, 4, 6}
A3 = {1, 3, 5}
A4 = {2, 3, 5}
A5 = {8, 9}

# Change them to tuples so they are hashable
superset = set((tuple(subset) for subset in [A1, A2, A3, A4, A5]))

# build families of all sets with a specific element
lookup = defaultdict(list)
for subset in superset:
    for element in subset:
        lookup[element].append(subset)

# If the families are small, brute force from there
pairs = set()
for __, family in lookup.items():
    for result in combinations(family, 2):
        pairs.add(result)

pprint (pairs)

如果连接不是稀疏的，这甚至可能比查看每一对都更糟糕。但如果是稀疏的，它可以是非常快的。