You are not logged in.
Pages: 1
I have a prodlem that seems like it needs set theory consepts for solving it.
I would like to have a roadmap from where to start looking since set theory is a large field.
My problem is :
I have 3 sets
A:{1,2,3,4,5}
B:{1,2,3}
C:{1,5}
and i want to count all possible sets D {x,y,z} that x belongs to A, y belongs to B, z belongs to C (similar to the cardinality of AxBxC) BUT there souldn't be any number more than one time (i.e. (1,2,1) should not be counted)
I know the answer for this problem is 15 but i need a formula for solving such problems without having to enumerate each solution (since the numbers of each set can be really high)
Thank you in advance.
Offline
For two sets, A and B, we remove one every time it is in the intersection of A and B. To see this, try your example:
(1, 1)
(1, 2)
(1, 3)
(2, 1)
(2, 2)
(2, 3)
(3, 1)
(3, 2)
(3, 3)
(4, 1)
(4, 2)
(4, 3)
(5, 1)
(5, 2)
(5, 3)
Since 1 is in the intersection, we remove (1,1). Since 2 is, we remove (2, 2) and since 3 is, we remove (3, 3). The result is that the answer will be:
|A x B| - |A n B|
Try to see if you can generalize this result to 3 sets.
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
Offline
Ok, so I came back to this an it's a bit more complicated than I had first thought for 3 sets. The final answer is:
|A x B x C| - |C|*|A n B| - |B|*|A n C| - |A|*|B n C| + 2*|A n B n C|
Here is the reasoning:
We take all 3-tuples (a, b, c) and we want to eliminate some because there are places where a = b, a = c, or b = c. We need to eliminate all pair where a = b. So we take out A n B. But for each element in A n B, it is paired with |C| element from C. So we need to remove |C|*|A n B|. The same logic applies to the other subtractions.
But wait, what if we have (1, 1, 1)? By the logic above, we would be removing this 3 times. But we can only remove it once. So we add it back in there twice with 2*|A n B n C|, as for this to happen, the element must be in all three sets.
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
Offline
Thank you for your responce .
I will try to see if the same logic can be applied to 4 sets since in my problem the number of sets can varry!
Offline
It can, but the formula will be very complicated.
With 2 sets, only 2 terms are required but 3 sets need 5. Jumping from 3 to 4 will need even more terms, and it would be easy to go wrong somewhere whilst counting those.
I'm not sure whether this is better or worse, but I'd do it by a kind of 'induction'. I'll use your example to demonstrate.
First we look for all single-element sets that can be made from A.
Obviously, these are:
{1}
{2}
{3}
{4}
{5}
Now we take every set in that list and add every element we can from B on to them.
{1,2} {1,3}
{2,1} {2,3}
{3,1} {3,2}
{4,1} {4,2} {4,3}
{5,1} {5,2} {5,3}
Now we take every set in that list and add elements from C.
{1,2,5}
{1,3,5}
{2,1,5}
{2,3,1} {2,3,5}
{3,1,5}
{3,2,1} {3,2,5}
{4,1,5}
{4,2,1} {4,2,5}
{4,3,1} {4,3,5}
{5,2,1}
{5,3,1}
I know that that's just listing the solutions, but it's a well-defined method for doing so and so you could probably get a computer to do all the work for you.
Why did the vector cross the road?
It wanted to be normal.
Offline
ok for anyone interested here is a java code that calculates such solutions ...
Vector<Integer> vr1 = new Vector<Integer>();
vr1.add(new Integer(1));
vr1.add(new Integer(2));
vr1.add(new Integer(3));
vr1.add(new Integer(4));
vr1.add(new Integer(5));
Vector<Integer> vr2 = new Vector<Integer>();
vr2.add(new Integer(1));
vr2.add(new Integer(2));
vr2.add(new Integer(3));
Vector<Integer> vr3 = new Vector<Integer>();
vr3.add(new Integer(1));
vr3.add(new Integer(5));
Vector<Vector<Integer>> vr = new Vector<Vector<Integer>>();
vr.add(vr1);
vr.add(vr2);
vr.add(vr3);
Vector<Integer[]> row = new Vector<Integer[]>();
for (int i = 0; i < vr.size(); i++)
{
if(i+1==vr.size())
break;
Vector<Integer> row1 = vr.get(i);
if(i==0)
{
// copy to row vector
for (int j = 0; j < row1.size(); j++)
{
Integer[] integer = new Integer[]{row1.get(j)};
row.add(integer);
}
}
Vector<Integer[]> newRow = new Vector<Integer[]>();
Vector<Integer> row2 = vr.get(i+1);
for (int j = 0; j < row.size(); j++)
{
Integer[] previousResult = row.get(j);
int resultSize = previousResult.length;
for (int j2 = 0; j2 < row2.size(); j2++)
{
Integer currentValue = row2.get(j2);
Integer[] tmpPreviousResults = new Integer[previousResult.length];
System.arraycopy(previousResult, 0, tmpPreviousResults, 0, previousResult.length);
Arrays.sort(tmpPreviousResults);
if(Arrays.binarySearch(tmpPreviousResults, currentValue)>=0)
{
// Already exist so skip
continue;
}
Integer[] newResult = new Integer[resultSize+1];
for (int k = 0; k < previousResult.length; k++)
{
newResult[k] = previousResult[k];
}
newResult[resultSize] = currentValue;
newRow.add(newResult);
}
}
row = newRow;
}
thank you very much for your effort.
Offline
Oh ... forgot ... for printing the result ( THE "row" Vector) :
private static void print(Vector<Integer[]> holder)
{
for (int i = 0; i < holder.size(); i++)
{
Integer[] v = holder.get(i);
for (int j = 0; j < v.length; j++)
{
System.out.print("\t"+v[j]);
}
System.out.print("\n");
}
}
Offline
Pages: 1