Перебор всех комбинаций элементов из заданных n множеств

#java #cpp #алгоритм #комбинаторика #множества

Как можно сгенерировать все возможные комбинации, состоящие из элементов заданных
n множеств ? Например, если имеется 3 множества:

A=1,2,3,4,...
B=a,b,c,d,...
C=A,B,C,D,...


и нужно получить что-то вроде:

1 a A; 
1 b A; 
1 c A
....
1 a B; 
1 b B


При этом число n заранее неизвестно, так что вложенными циклами решить не получается.
    

Ответы

Ответ 1

Представьте себе, что это - цифры, стоящие на соответствующих местах числа.

Создаем первое число - 1aA (или сколько там нужно мест). Потом просто увеличиваем
последний элемент, пока не переберем все. После этого выставляем его равным минимальному
элементу и увеличиваем предыдущий (если он тоже максимален - сбрасываем его в минимум
и переходим к предыдущему).

1aA
1aB
1aC  // достигли максимума в последней позиции. переход-
1bA
1bB
1bC  // достигли максимума в последней позиции. переход-
1bA
1bB
1bC  // достигли максимума в последней позиции. переход-
1bA
1bB
1bC  // достигли максимума в последней позиции. переход-
1сA
1сB
1сC  // достигли максимума в последней позиции. переход- но во второй позиции
     // тоже максимум, перенос далее
2aA
...


Словом, просто реализуем алгоритм M (Генерация в смешанной позиционной системе счисления)
со страницы 330 4А тома "Искусства программирования"...