确定一个集合与另外两个集合的交集是否为空
对于任何三个给定的集合 A、B 和 C:有没有办法(以编程方式)确定 A 中是否有一个元素是 B 和 C 的合取(编辑:交集)的一部分?
示例:
A:所有大于3的数字
B:所有小于7的数字
C:所有等于 5 的数字
在这种情况下,集合 A 中有一个元素(即数字 5)适合。我将其作为规范来实现,因此这个数字范围只是一个示例。 A、B、C 可以是任何东西。
For any three given sets A, B and C: is there a way to determine (programmatically) whether there is an element of A that is part of the conjunction (edit: intersection) of B and C?
example:
A: all numbers greater than 3
B: all numbers lesser than 7
C: all numbers that equal 5
In this case there is an element in set A, being the number 5, that fits. I'm implementing this as specifications, so this numerical range is just an example. A, B, C could be anything.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
发布评论
评论(3)
如果我正确理解你的问题,你想以编程方式计算 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;
}
这个问题需要进一步澄清。
首先,您想使用范围给出的符号集吗?
其次,这是一个一次性问题还是会以某种形式重复(如果是,问题的稳定部分是什么?)?
如果您想使用范围,那么您可以用二叉树表示它们,并在这些结构上定义并集和交集运算。构建树需要 O(n log n),查找结果需要 O(log n)。仅使用树集不会带来回报,但它可以灵活地有效支持范围的任何组合(如果这就是您所认为的“它可以是任何东西”)。
另一方面,如果有任何意思,任何元素集,那么唯一的选择就是枚举元素。在这种情况下,在集合 B 和 C 上构建 B+ 树也需要 O(n log n) 时间,但这里 n 是元素的数量,在第一种情况下 n 是范围的数量。后者可能大几个数量级,当然它只能表示有限数量的元素。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
编辑:
谢谢尼基!
如果
B.Count <= C.Count <= A.Count
将会很有帮助。请参阅高效集交集算法。
我们可以使用集合的分配律
EDIT:
Thanks Niki!
It will be helpful if
B.Count <= C.Count <= A.Count
.Look at Efficient Set Intersection Algorithm.
We can use distributive laws of sets