Make possible combinations

Question

Algorithms

Task - there are several sets - {A1, A2, A3, ...}, {B1, B2, B3, ...}, {C1, C2, C3, ...}, etc., it is necessary to compose all possible combinations of elements in such a way that the combination contains one and only one element from each set:
A1, B1, C1
A2, B1, C1
A3, B1, C1
A1, B2, C1
, etc.

Prompt please the most competent algorithm.

Answer 1

Nested loops?

Answer 2

for (int i = 0; i < a.count; i++)
for (int k = 0; k < b.count; k++)
for (int j = 0; j < c.count; j++)
count << a[ i] << b[k] << c[j]

Answer 3

There is also
- a variant with recursion to a depth equal to the letter
and
- a variant with one cycle from 0 to ACount*BCount*...*ZCount-1 and then determining all the current mod / div indexes.

Answer 4

And ... Oh ... Sipets. Sorry for the comments and the previous answers, I didn’t understand that the number of sets is not a constant.
Answer:
If there is an array A of sets/arrays Ai, the algorithm is as follows:
int c = 1;
int* divs = new int[A.count];
divs[A.count - 1] = 1;
for (int i = A.count -2; i >= 0; i++)
divs[i] = divs[i+1]*A[i].count;
for (int i = 0; i < A.count; i++) c *= A[i].count; //c — number
int i = 0;
while (i < c)
{
for (int k = 0; k < A.count; k++)
cout << (i / divs[k]) % A[k].count;
count << endl;
i++;
}
Something like this. This is what OLS was talking about. — a variant with one cycle from 0 to ACount*BCount*...*ZCount-1 and then determination of all current indexes mod/div.

Answer 5

It still seems to me that through recursion it is written faster, there is less chance of making a mistake:

procedure Recur(iLevel:integer);
var i:integer;
begin
if iLevel=iLevelCount then Process(X)
                      else
   for i:=0 to Ai[iLevel].Count-1 do
       begin
       X[iLevel]:=Ai[iLevel][i];
       Recur(iLevel+1)
       end;
end;

recur(0);

Answer 6

python:

import itertools

sets = ( ('A1', 'A2', 'A3'), ('B1', 'B2', 'B3'), ('C1', 'C2', 'C3') )

combinations = itertools.product(*sets)