3
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ So you want a function that takes in an array of arrays and returns back a new array of arrays that is the single element product of the initial array, right? Ideally in JavaScript I assume? $\endgroup$
    – ssmith
    May 15 '20 at 14:31
  • $\begingroup$ @ssmith Correct. Doesn't have to be in JS. Any C-like syntax or pseudo-code I should be able to understand. $\endgroup$ May 15 '20 at 14:47
  • 1
    $\begingroup$ My attempt in Java: twitter.com/macerub/status/1261331142227173377?s=19 $\endgroup$ May 15 '20 at 18:21
2
$\begingroup$

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))   
$\endgroup$
5
  • $\begingroup$ Cool. This works for me. I implemented it in JavaScript. I wonder which approach, out of yours and the one proposed by @Steven, is more performant. $\endgroup$ May 15 '20 at 16:50
  • 1
    $\begingroup$ I believe @Steven's answer doesn't produce output in terms of the sets you input, but rather the output is a sequence of integers, which isn't quite what you asked for. It also only works when all subsets are of the same size. (I can't comment on his answer directly.) $\endgroup$
    – ludog
    May 15 '20 at 18:55
  • 2
    $\begingroup$ The big-O complexity is always going to be exponential. In particular, it can't get any better than the product of sizes of all the subsets, because you need to generate that many elements. If performance is important, it will probably be language-specific tweaks that make the difference. $\endgroup$
    – ludog
    May 15 '20 at 18:59
  • 1
    $\begingroup$ The question asks to generate all combinations. It is unclear if it is a requirement for them to be explicitly stored in an output collection. This sounds like nitpicking but might be relevant depending on what these combinations are used for. For example, if they are used to compute some additive function of the elements (e.g., elements are an integers and we want all possible sums of valid combinations) then one can compute all the values of the function in time $\Theta(k^n)$, while any algorithm that stores all combinations must take time $\Omega(nk^n)$ since this is the size of the output. $\endgroup$
    – Steven
    May 15 '20 at 23:02
  • $\begingroup$ @Steven apologies if the question wasn't as clear as it could have been. That being said, ludog understood exactly what I was looking for and his algorithm uses the inputs and outputs from my example which is exactly what I was looking for. If you feel the question is misleading, let me know how I can edit it to better state the requirements. $\endgroup$ May 15 '20 at 23:13
3
$\begingroup$

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;
$\endgroup$
4
  • $\begingroup$ Pseudo-code for this approach would be awesome. $\endgroup$ May 15 '20 at 15:31
  • 1
    $\begingroup$ I added the pseudocode to my answer $\endgroup$
    – Steven
    May 15 '20 at 15:38
  • $\begingroup$ Thanks for your answer. I may have misunderstood parts of your pseudocode but my implementation of it gets stuck in an infinite loop. Would you have the patience and kindness to add an actual code example to your answer. Any C-like syntax I should be able to understand. $\endgroup$ May 15 '20 at 16:48
  • 1
    $\begingroup$ Here is a small implementation in C++14. $\endgroup$
    – Steven
    May 15 '20 at 17:51

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.