5
$\begingroup$

Unfortunately I could neither find nor develop a closed formula, but I believe there is a simple solution for this problem. Could you please help me?

Suppose that there are 4 different sets:

Set A, elements: A1, A2, A3, A4

Set B, elements: B1, B2, B3

Set C, elements: C1, C2, C3

Set D, elements: D1

Each of the elements in a set differes from the other, so A1 is not the same as A2.

How many new different sets can be created from the elements form any 3 of the all (4) sets (Set A, Set B, Set C and Set D) if I can choose only one element form one set? Picking order is not important - (A1, B1, C1) and (A1, C1, B1) are the same. (A1, A2, B1) is not allowed, because both A1 and A2 come from the same A set.

So I may choose 1-1 element form A, B, C or A, B, D or A, C, D, or B, C, D.

Basically I am interested in a general solution.

It can be solved with an algorithm, but it requires time and several loops, especially when the sets are large.

Here is my code: (According to it the answer is 69.)

int A[5] = { 1, 2, 3, 4};
int B[4] = { 5, 6, 7 };
int C[4] = { 8, 9, 10 };
int D[2] = { 11};
int *a[4] = { A, B, C, D };

int size[4] = { 4, 3, 3, 1 };

int num = 0;
for (int s1 = 0; s1 < 4; s1++)
{
    for (int s2 = s1 + 1; s2 < 4; s2++)
    {
        for (int s3 = s2 + 1; s3 < 4; s3++)
        {
            //Sets are choosen.

            for (int i = 0; i < size[s1]; i++)
            {
                for (int j = 0; j < size[s2]; j++)
                {
                    for (int k = 0; k < size[s3]; k++)
                    {
                        num++;
                        cout << a[s1][i] << "  " << a[s2][j] << "  " << a[s3][k] << endl;
                    }
                }
            }




        }
    }
}
cout << "NUM: " << num;

Thanks in advance!

$\endgroup$
9
  • $\begingroup$ By choosing 3 elements, do you mean how many possible sets of 3 elements there would be, or how many times you can draw 3 elements without replacement? If you want to draw 3 elements without replacements, the answer will depend on the number of sets. If there are 3 sets, it depends on the size of the two smaller sets. If there are 4 sets (as in your case), it will become more complicated and depend on the relative size of all the sets. Clarifying your answer will help other answer it. $\endgroup$ May 28, 2015 at 14:10
  • $\begingroup$ Please add the [self-study] tag & read its wiki. $\endgroup$ May 28, 2015 at 14:36
  • $\begingroup$ OK, I improved my question, I hope it's more specific now. Thanks for reminding me for the self-study flag. (However it's not a homework, I just had some argument over this problem.) $\endgroup$
    – cgergo
    May 28, 2015 at 14:52
  • $\begingroup$ It's simply 4*3*3*1=36 $\endgroup$
    – Aksakal
    May 28, 2015 at 15:53
  • 1
    $\begingroup$ Assume no two sets have common elements. Let the set sizes be $a,b,c,d$. The question asks for $$abc + abd + acd + bcd = abcd(1/a+1/b+1/c+1/d)=69.$$ Whether or not this is an appropriate answer depends on how you conceive of the "general solution." Exactly what do you propose as the general problem? Will you always be picking one less element than there are sets? $\endgroup$
    – whuber
    May 28, 2015 at 17:19

1 Answer 1

3
$\begingroup$

If you need only three sets at a time, then 4*3*3+4*3*1+4*3*1+3*3*1=69 is your answer. Here how it goes.

You first select the sets to pull from: ABC, ABD, ACD and BCD. You know the binomial formula to check the number: $\frac{4!}{3!(4-3)!}=4$

Next, for each three sets you pick the elements: A1,B1,C1 etc. You know the formula: $n_A\cdot n_B\cdot n_C$

$\endgroup$
2
  • $\begingroup$ What happens if we had $A_1 = \{A_{11}, \dots, A_{1n} \}, \dots, A_n = \{A_{n1}, \dots, A_{nj} \}$ where $n$ is large and the cardinalities of the sets were different? We would have to look at $\binom{n}{3}$ combinations of three sets. $\endgroup$ May 28, 2015 at 17:57
  • $\begingroup$ @missingdataguy, it's a big number, but not as big: $\frac{n!}{3!(n-3)!}$. It doesn't matter in which order you pick sets, and in which order are the unpicked sets. $\endgroup$
    – Aksakal
    May 28, 2015 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.