检查集合的集合是否成对不相交 [英] Check if a collection of sets is pairwise disjoint

问题描述

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

What is the most efficient way to determine whether a collection of sets is pairwise disjoint? -- i.e. verifying that the intersection between all pairs of sets is empty. How efficiently can this be done?

推荐答案

预期线性时间O（元素总数）：

Expected linear time O(total number of elements):

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

在假设您的输入是表示为某种无序数据结构（哈希表？）的集合的集合的情况下，这是最佳选择，因为您需要至少每个元素都看一次。

This is optimal under the assumption that your input is a collection of sets represented as some kind of unordered data structure (hash table?), because than you need to look at every element at least once.

通过对集合使用不同的表示，可以做得更好。例如，通过维护一个全局哈希表，该哈希表为每个元素存储存储在其中的集合的数量，您可以最佳地执行所有集合操作，还可以检查O（1）中的不相交性。

You can do much better by using a different representation for your sets. For example, by maintaining a global hash table that stores for each element the number of sets it is stored in, you can do all the set operations optimally and also check for disjointness in O(1).

这篇关于检查集合的集合是否成对不相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！