Determine if the intersection of a set with the conjunction of two other sets is empty
For any three given sets A, B and C: is there a way (programmatically) to determine if an element A exists that is part of the conjunction (edit: intersection) of B and C?
Example:
A: all numbers greater than 3
B: all numbers less than 7
C: all numbers equal to 5
In this case, there is an element in set A that is the number 5 that fits. I am implementing this as a spec, so this numerical range is just an example. A, B, C can be anything.
a source to share
EDIT: Thanks Niki!
It will be helpful if 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;
}
Take a look at Efficient Cross-intersection Algorithm .
We can use distributive set laws
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
}
a source to share
If I understand your question correctly, you want to compute the intersection of three sets programmatically, right? You want to see if there is an element in A that exists at the intersection of B and C, or in other words, you want to know if the intersection of A, B and C is non-empty.
Many languages have containers and intersection algorithms installed, so you should just use them. Your example in 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;;
This outputs false since the intersection of a and b is not empty (contains 5). This, of course, depends on whether the members of the set are comparable (in the example, the function comparison defines this property in the Int module).
Alternatively in 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;
}
a source to share
The question needs further clarification. First, do you want to work with symbolic sets given by a range? And second, is it a question once, or will it be repeated in one form or another (if so, what are the stable parts of the question?)?
If you want to work with ranges, you can represent them with binary trees and define the union and intersection operations of these structures. It takes O (n log n) to build a tree, and O (log n) to find the result. It doesn't pay off with just sets of trees, but it would be flexible to efficiently support any combination of ranges (if that's what you thought, "it could be anything").
On the other hand, if anything means any set of items, then the only option is to enumerate items. In this case, building trees B + on sets B and C will also take O (n log n) time, but here n is the number of elements, and in the first case n is the number of ranges. Later it can be several orders of magnitude larger, and of course it can only represent a finite number of elements.
a source to share