Составить возможные комбинации

Question

[Дмитрий]

Задача — есть несколько множеств — {A1, A2, A3, ...}, {B1, B2, B3, ...}, {C1, C2, C3, ...} и т.д., необходимо составить все возможные комбинации элементов таким образом, чтобы в комбинации присутствовал один и только один элемент из каждого множества:
A1, B1, C1
A2, B1, C1
A3, B1, C1
A1, B2, C1
и т.д.

Подскажите плиз наиболее грамотный алгоритм.

Comments

[Дмитрий]

забыл уточнить, что количество множеств можеть быть разным, может быть 3, а может и 30. другими словами есть динамический массив, элементы которого есть множества. и надо перебрать комбинации из всех множеств этого массива. видимо без рекурсии не обойтись

[TheHorse]

Зачем?! Чем вам цикли не нравятся?

[Дмитрий]

циклы мне очень нравтся :) просто не получается тут одними циклами обойтись. количество множеств может быть разным, как я уточнил, а алгоритм универсальным. то есть если будет 30 множеств не хотелось бы писать вручную 30 вложенных циклов. ну я примерно понял, куда нужно копать (для c# разработчиков). разбираюсь

[TheHorse]

Да, прошу прощения, бывает. Уже понял. Написан ответ для любого количеств множеств, без рекурсии.

[Андрей]

И с рекурсией вариант тоже добавлен («для комплекта»).

[1010101001000100110100111]

>> количество множеств можеть быть разным, может быть 3, а может и 30

фига се Вы тут губищи раскатали. 30 множеств. Вы че?
даже простенькая прикидка: берем 30 множеств по два элемента в каждом:
в итоге имеем 2^30 сочетаний на выходе.
Вот уж интересно, как Вы собираетесь ВОЗВРАЩАТЬ результат из МИЛЛИАРДА элементов (по 30 байт минимум каждый).
Вы своей выдачей не только всю оперативу переполните, но и любой винт в файловой системе FAT32 (даже если выдачу разобьете на 8 фрагментов по 4 Гигабайта).

Answer 1

[Сергей Береснев]

Вложенные циклы?

Answer 2

[TheHorse]

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]

Comments

[korvindest]

Думаю что при N наборов ваш вариант станет каторгой.
Если конечно вы имели ввиду отдельный цикл под каждый набор

[TheHorse]

Количество вариантов — a.count * b.count * c.count. Это не очевидно? То бишь, в любом случае нужно будет пройтись по всем. То, что я написал — не имеет избыточной сложности, потребления памяти. Не понятно, что вам не нравится?

[Smileek]

, для огромного количества N можно сначала инициализировать массив массивов.
Но вопрос был об алгоритме, а он как раз останется тем же самым.

[korvindest]

Я полностью согласен, с тем что сложность неизбежно будет произведением по всем count и мало того прекрасно понимаю что ваш вариант рабочий, но человека может запутать ваша реализация и когда у него будет 50 массивов, он напишет 50 вложенных циклов. В остальном возражений нет.

Answer 3

[Андрей]

Есть еще
— вариант с рекурсией до глубины, равной букве
и
— вариант с одним циклом от 0 до ACount*BCount*...*ZCount-1 и затем определением всех текущих индексов mod/div-ом.

Comments

[TheHorse]

И все эти варианты медленней чем вложенные цикли… Ребят, вы чего?! Что тут происходит? Это шутки какие-то, или что?
Можно даже динамическое программирование прикрутить, и поск в ширину, но зачем?!

[Сергей Береснев]

Тут дело то в чём? В том, что количество их может быть разное. Т.е. изначально в вопросе читалось про три множества. Поэтому и пришли в голову три вложенных цикла. Но появилось дополнение к вопросу и выяснилось, что количество множеств варьируется. Тут уже надо как раз использовать варианты OLS, потому что для вложенных циклов надо заранее знать количество множеств.

[TheHorse]

Да, спасибо, уже понял.

Answer 4

[TheHorse]

А… Ой… Сипец. Простите за комменты и предидущие ответы, не осилил, что количество множеств — не константа.
Ответ:
Если есть массив A множеств /массивов Ai, алгоритм таков:

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 — количество

int i = 0;
while (i < c)
{
for (int k = 0; k < A.count; k++)
cout << (i / divs[k]) % A[k].count;
count << endl;
i++;
}

Как-то так. Это то о чем говорил OLS. — вариант с одним циклом от 0 до ACount*BCount*...*ZCount-1 и затем определением всех текущих индексов mod/div-ом.

Comments

[whataboutio]

Вы, наверное, в первом цикле имели ввиду i--?

divs[A.count — 1] = 1;
for (int i = A.count -2; i >= 0; i++)
divs[i] = divs[i+1]*A[i].count;

[TheHorse]

да

Answer 5

[Андрей]

мне все-таки кажется, что через рекурсию это быстрее пишется, меньше шанс ошибиться:

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

[Ano]

python:

import itertools

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

combinations = itertools.product(*sets)

Comments

[Дмитрий]

да, спасибо. по крайней мере я понял, что мне нужен алгоритм для cartesian product (только для c#), хотя казалось бы это было очевидно с самого начала :)