检查集合集合是否成对不相交。

Question

确定集合集合是否成对不相交的最有效方法是什么？--即验证所有对集之间的交集是空的。这样做的效率有多高？

Answer 1

预期线性时间O(元素总数)：

def all_disjoint(sets):
    union = set()
    for s in sets:
        for x in s:
            if x in union:
                return False
            union.add(x)
    return True

假设输入是一组集合，表示为某种无序的数据结构(哈希表？)，这是最优的，因为至少需要查看每个元素一次。

通过对集合使用不同的表示形式，您可以做得更好。例如，通过维护一个全局哈希表，为每个元素存储其存储的集合数，您可以最优地执行所有set操作，还可以检查O(1)中的不一致性。

Answer 2

集合中的集合是成对不相交的当且仅当它们的联合的大小等于它们的大小之和(此语句适用于有限集)：

def pairwise_disjoint(sets) -> bool:
    union = set().union(*sets)
    return len(union) == sum(map(len, sets))

这可能是一个单线，但可读性计数。

Answer 3

使用Python作为psudo代码。对每对集合的交集只进行一次以下测试。

def all_disjoint(sets):
    S = list(sets)
    while S:
        s = S.pop()  # remove an element
        # loop over the remaining ones
        for t in S:
            # test for intersection
            if not s.isdisjoint(t):
               return False
    return True

交叉测试的数目与具有相同顶点数的完全连通图中的边数是相同的。如果发现任何对没有不相交，它也会提前退出。