代码之家 › 专栏 › 技术社区 › koen

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

set-theory specifications set algorithm

koen · 技术社区 · 15 年前

对于任意三个给定的集合A、B和C:有没有一种方法(以编程方式)确定A的元素是否是B和C的连接(编辑:交集)的一部分?

例子:

B:所有数字都小于7
C:所有等于5的数字

3 回复 | 直到 15 年前

Community CDub 8 年前

谢谢尼基!

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;
}

Efficient Set Intersection Algorithm .

distributive laws of sets

$alt text$

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
}

Niki Yoshiuchi 15 年前

如果我对你的问题理解正确,你想通过编程计算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;;

#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;
}

Unreason 15 年前

这个问题需要进一步澄清。第二,这是一个一次性的问题,还是会以某种形式重复(如果是的话,问题的稳定部分是什么?)?

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