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?


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.

  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)
    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
  • $\begingroup$ I lost you from the first line :( could you please explain more? Thanks! $\endgroup$
    – Jarvis
    Oct 14 '19 at 8:03
  • $\begingroup$ @Jarvis Try reading it again. $\endgroup$ Oct 14 '19 at 10:55

Your Answer

