确定一组与其他两组结合的交集为空

Question

有关的任意三个给定的集合A，B和C：有一种方法来确定（通过编程）是否存在是结合（编辑：交点）的部分A的元件？B和C

的

例如：结果 答：所有的数字大于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个集的交集，对不对？要看看是否有所述的存在于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;;

这个输出假，作为B和C的交点是非空的（包含5）。这当然依赖于以下事实，该组中的元素是可比较的（在本例中，函数比较限定诠释模块在本属性）。

可选地，在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 +上套B和C的树木也需要为O（n log n）的时间，但在这里，n是元件的数量，并且在第一种情况下，n是范围的数量。后来可能是更大的数量级的几个数量级，当然它只能表示元素的有限数。