确定一个集合与另外两个集合的交集是否为空

Question

对于任何三个给定的集合 A、B 和 C：有没有办法（以编程方式）确定 A 中是否有一个元素是 B 和 C 的合取（编辑：交集）的一部分？

示例：
A：所有大于3的数字
B：所有小于7的数字
C：所有等于 5 的数字

在这种情况下，集合 A 中有一个元素（即数字 5）适合。我将其作为规范来实现，因此这个数字范围只是一个示例。 A、B、C 可以是任何东西。

Answer 1

编辑：
谢谢尼基！

如果 B.Count <= C.Count <= A.Count 将会很有帮助。

D = GetCommonElements(B,C);
if( D.Count>0 && GetCommonElements(D,A).Count >0)
{
    // what you want IS NOT EMPTY
}
else
{
    // what you want IS EMPTY
}

SET GetCommonElements(X,Y)
{
    common = {}
    for x in X:
       if Y.Contains(x):
         common.Add(x);
    return common;
}

请参阅高效集交集算法。

---

我们可以使用集合的分配律

if(HasCommonElements(A,B) || HasCommonElements(A,C))
{
    // what you want IS NOT EMPTY
}
else
{
    // what you want IS EMPTY
}

bool HasCommonElements(X,Y)
{
    // if at least one common element is found return true(immediately)

    return false
}

Answer 2

如果我正确理解你的问题，你想以编程方式计算 3 个集合的交集，对吧？你想看看A中是否有一个元素存在于B和C的交集中，或者换句话说，你想知道A、B和C的交集是否非空。

许多语言已经设置了容器和交集算法，因此您应该能够使用它们。 OCaml 中的示例：

module Int = struct
    type t = int
    let compare i j = if i<j then -1 else if i=j then 0 else 1
end;;

module IntSet = Set.Make(Int);;

let a = List.fold_left (fun a b -> IntSet.add b a) IntSet.empty [4;5;6;7;8;9;10];;
let b = List.fold_left (fun a b -> IntSet.add b a) IntSet.empty [0;1;2;3;4;5;6];;
let c = IntSet.add 5 IntSet.empty;;

let aIbIc = IntSet.inter (IntSet.inter b c) a;;
IntSet.is_empty aIbIc;;

输出 false，因为 ab 和 c 的交集非空（包含 5）。这当然依赖于集合的元素是可比较的这一事实（在示例中，函数 Compare 在 Int 模块中定义了此属性）。

或者在 C++ 中：

#include<iostream>
#include<set>
#include<algorithm>
#include<iterator>

int main()
{
    std::set<int> A, B, C;

    for(int i=10; i>3; --i)
        A.insert(i);
    for(int i=0; i<7; ++i)
        B.insert(i);
    C.insert(5);

    std::set<int> ABC, BC;
    std::set_intersection(B.begin(), B.end(), C.begin(), C.end(), std::inserter(BC, BC.begin()));
    std::set_intersection(BC.begin(), BC.end(), A.begin(), A.end(), std::inserter(ABC, ABC.begin()));

    for(std::set<int>::iterator i = ABC.begin(); i!=ABC.end(); ++i)
    {
        std::cout << *i << " ";
    }
    std::cout << std::endl;

    return 0;
}

Answer 3

这个问题需要进一步澄清。
首先，您想使用范围给出的符号集吗？
其次，这是一个一次性问题还是会以某种形式重复（如果是，问题的稳定部分是什么？）？

如果您想使用范围，那么您可以用二叉树表示它们，并在这些结构上定义并集和交集运算。构建树需要 O(n log n)，查找结果需要 O(log n)。仅使用树集不会带来回报，但它可以灵活地有效支持范围的任何组合（如果这就是您所认为的“它可以是任何东西”）。

另一方面，如果有任何意思，任何元素集，那么唯一的选择就是枚举元素。在这种情况下，在集合 B 和 C 上构建 B+ 树也需要 O(n log n) 时间，但这里 n 是元素的数量，在第一种情况下 n 是范围的数量。后者可能大几个数量级，当然它只能表示有限数量的元素。