检查一组集合是否两两不相交

Question

最有效的方法是确定一个集合的集合是否两两不相交，即验证所有集合对的交集是否为空。这可以在多大程度上实现高效？

- Robert T. McGibbon

---

我对你的问题持谨慎态度。它的高效完成取决于许多因素，如集合的大小、集合的数量、集合之间的重叠等等。 - Niklas B.

你也可以通过不同的方式来维护你的集合，使得这个操作比起原本需要查看所有元素的O(n)下限更加高效。 - Niklas B.

顺便问一下：你是如何表示你的集合的？你对它们执行了哪些操作？ - Niklas B.

对于仅有的两个列表，可以参考以下链接中的Python代码来测试它们是否共享任何项：Test if lists share any items in python - Stack Overflow - user202729

Answer 1

如果且仅当集合中所有元素互不相同时，集合的大小之和等于它们的并集大小（此语句适用于有限集合）：

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

这可能只是一个简单的一行代码，但是可读性至关重要。

- 0 _

Answer 2

预计线性时间复杂度为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) 中执行所有集合操作并检查是否不相交。

- Niklas B.

---

这是对内置函数 all 进行重载，对吧？最好使用不同的变量名。 - tscizzle

Answer 3

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

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

交集测试的次数与具有相同数量顶点的完全连接图中的边数相同。如果发现任何一对不是不相交的，则会提前退出。

- Dan D.