2
$\begingroup$

I'm wokring on this problem for a while. I want to know:

  1. The correct name of this problem, so I can look it up in textbooks\online.

Here is the problem descirption: enter image description here

The (un-ordered) combinations to be generated are:

  • of 1 item size: {a1}, {a2} .... {c4}
  • of 2 items size: {a1, b1}, {a1, b2} ... {b2, c4}
  • of 3 items size: {a1, b1, c1}, ... {a3, b2, c4}

The question is: Given any number of sets M where each set has distinc number of items, How many (un-ordered) combinations are there of size 1, 2, ..., up to M? And how to generate those combinations?

$\endgroup$
2
$\begingroup$

Let's solve your example question first. Say, we want to know the number of combinations of size 2 possible from $A, B, C$. This would be equal to

  1. for each element in $A$, pair it with each element in $B$. This gives us $|N_A||N_B|$ combinations of size 2.
  2. for each element in $A$, pair it with each element in $C$. This gives us $|N_A||N_C|$ combinations of size 2.
  3. for each element in $B$, pair it with each element in $C$. This gives us $|N_B||N_C|$ combinations of size 2.

In total, this gives us as $ |N_A||N_B|+|N_A||N_C|+|N_B||N_C| = 3\times2 + 3\times4 + 2\times4 = 26$

What we have done above is to take all possible combinations of the sets in $M$ (set combinations of size 2 are $AB, AC, BC$), taken the product of all their sizes, and finally added them up.

In general, given $n$ sets in $M$, and we want to know the number of $k$ sized combinations. The high-level algorithm would be as follows

for each k-sized set combination of sets in M
  multiply the sizes of all the sets in the k-size set combination 
  add this product to the final result

This can be written briefly as $$ \sum_{\substack{S \subseteq M\\|S|=k}}\prod_{X\in S}{|X|}$$

Now, to generate all unordered combinations of size $k$, we follow the same steps as the above algorithm, but instead of taking the product of set sizes, we perform a cross product on all the sets in each $k$-size set combination.

Combinations(M,k):
  if |M| == 1
    return { {e} | e in any set of M }

  M[1] = first set in M

  if |M| > k
    Result = Combinations(M\{M[1]} ,k)
  else
    Result = {}

  Temp = Combination(M\{M[1]},k-1)

  for each element e in M1:
    make a copy of Temp called Dummy
    to each set in Dummy, add e
    add all the elements in Dummy to Result

  return Result
$\endgroup$
  • $\begingroup$ I lost you from the first line :( could you please explain more? Thanks! $\endgroup$ – Jarvis Oct 14 at 8:03
  • $\begingroup$ @Jarvis Try reading it again. $\endgroup$ – RandomPerfectHashFunction Oct 14 at 10:55

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.