1
$\begingroup$

We have 3 Data Sets. From each set we will be selecting few numbers. 3 from Set 1, 2 from Set 2, 3 from Set 3. Totally, we will get 8 Numbers from 3 Sets. The resulting sets shouldn't contain any duplicates.

My question is, How can we know whether we can generate the sets, each containing 8 numbers without duplicates or not? If we can generate, then how many combinations can we generate? What formula should we use?

I am adding the images for the better illustration of the problem statement. enter image description here enter image description here

Note: I have tried for the Permutations and Combinations, but I am not sure as how to solve this mathematical model. Any suggestions or references to solve this will be highly appreciated. I am not sure about the sections this problem falls under.

$\endgroup$
2
  • 1
    $\begingroup$ As for knowing whether generating such a set is possible or not, check whether each individual set has a cardinality greater than or equal to your requirement from that set, (for eg, whether set1 has more than or equal to 3 elements) and check wether the union of all the sets has a cardinality greater than or equal to your total requirement (8 in this case). $\endgroup$
    – Aritra Das
    Aug 3 '15 at 18:36
  • $\begingroup$ Hi Aritra, Thanks for pointing me towards 'Cardinality'. Yes, it will surely help me in first level check whether the combination is possible or not. So it forms one level of check for me. :-) $\endgroup$ Aug 4 '15 at 13:03
1
$\begingroup$

I doubt you'll find anything useful to apply by hand, since the result depends on so many details of the overlaps of the sets, but here's something you can do if you want to solve the problem computationally but your sets are too large for brute force enumeration to be feasible.

Sort all elements according to which sets they occur in, i.e. label them with an element of $\{0,1\}^3$, where each component signifies membership in one of the three sets. The elements you select from the first set can have any of the four labels with first component $1$, and there are $\binom63$ ways of selecting three such labels. Likewise, for choosing two elements of the second set, you need to choose two of the four labels with second component $1$, in $\binom53$ ways, and then another $\binom63$ ways to choose three of the four labels with third component $1$. That gives you $20\cdot10\cdot20=4000$ label combinations, but they're not all different, since the same label may occur in more than one of the three selections. For each combination, add up the three contributions for each label, giving you a count of elements with that label to be selected. Retain only inequivalent combinations (i.e. with different total label counts), and add up the numbers of ways to choose elements with the specified labels (which are just products of binomial coefficients).

It's a bit of bookkeeping, but it only takes a couple of thousand operations and not the astronomical effort of enumeration if you have big sets.

$\endgroup$
1
  • 1
    $\begingroup$ Hi @Joriki, thanks for your answer. I will try your suggestion. I will let you know if I face any issues. Once again thanks for your suggestion. I highly appreciate that. $\endgroup$ Aug 3 '15 at 12:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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