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

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

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

您可以通过为集合使用不同的表示来做得更好.例如,通过维护一个全局哈希表,为每个元素存储它所存储的集合的数量,您可以最佳地执行所有设置操作,并检查O(1)中的不相交性.

Answer 2

当且仅当集合的并集的大小等于它们的大小之和时，集合中的集合才成对相交（此语句适用于有限集合）：

def pairwise_disjoint(sets):
    union = set().union(*sets)
    n = sum(len(u) for u in sets)
    return n == len(union)

这可能是一个单行，但是可读性很重要。