Combinations and Permutations of M sets of distinct items?

Question

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:

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?

Answer 1

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