Algorithm to generate combinations of n elements from n sets of m elements

Question

Suppose I have 3 sets of 2 elements: [A, B], [C, D], [E, F], and I wanted to generate all possible combinations of 1 element from each set, such that the result of the algorithm would be:

[A, C, E], [A, C, F], [A, D, E], [A, D, F], [B, C, E], [B, C, F], [B, D, E], [B, D, F]

What algorithm can I use to generate all combinations. Keep in mind that I'm looking for an algorithm that will work on any number of sets that have any number of elements, the above is just an example. Also, remember that I'm looking for an algorithm to actually generate the combinations, not just count them.

Answer 1

You can use recursion.

def recursive_generate(S):
    IF #S = 1:
        s <-- the single set in S
        return {{item} | item \in s}
    END IF
    S' <-- {}
    s <-- some selected set from S
    FOR item in s:
        For r in recursive_generate(S\{s}):
            S' <-- S' \union (r \union {item})
        END FOR
    END FOR
    RETURN S'

A python implementation:

def rec_gen(x):                                                                    
    if len(x) == 1:                                                                 
          return [[item] for item in x[0]]                                           
      appended = []                                                                  
      for s_el in x[0]:                                                              
          for next_s in rec_gen(x[1:]):                                              
              appended.append([s_el] + next_s)                                       
      return appended                                                                

given_s =[['A', 'B'], ['C', 'D'], ['E', 'F']]                                                                                                            
print(rec_gen(given_s))   

Answer 2

If you have $n$ sets of $k$ elements, your problem is equivalent to that of generating all numbers with up to $n$ digits in base $k$ (where the $i$-th digit of a number represents the index of the element to select from the $i$-th group).

This can easily be done by starting from the number $(00\dots000)_k$ and iteratively adding $1$. Let $d_i$ be the $i$-th least significant digit. Start from $i=1$ and do the following: if $d_i < k-1$ the next number is obtained by increasing $d_i$ by $1$. Otherwise set $d_i =0$, increase $i$ by $1$ and repeat. When $i$ reaches $n+1$ you know that you have already generated all the numbers and you can stop.

This procedure takes $O(k^n)$ time (assuming that $k$ fits in a constant number of memory words). To see this notice that you need to update $d_1$ every time you increment the number, $d_2$ changes only every $k$ increments, etc. In general $d_i$ changes every $k^{i-1}$ increments.

Since the total number of increments is $k^n$, the total number of operations is: $$ O\left(\sum_{i=1}^n \frac{k^n}{k^{i-1}} \right) = O\left(\sum_{i=1}^n k^{n-i+1} \right) = O\left(k \cdot \sum_{i=0}^{n-1} k^i \right) = O\left(k \cdot \frac{k^n - 1}{k-1} \right) = O(k^n). $$

This time complexity is asymptotically optimal because $\Omega(k^n)$ is a trivial lower bound (as there are $k^n$ distinct combinations to return).

A pseudocode:

A = An array of n integer elements, indexed from 1;
for i=1,...,n: A[i]=0;

while true:
    //A contains a n digit number in base k. Do something with it 

    i = 1;
    while i<=n and A[i]==k-1:
        A[i]=0;
        i=i+1;

    if i>n:
        return;  //We have already seen all n-digits numbers in base k
    else:
       A[i]=A[i]+1;