Рассмотрим алгоритм получения декартова произведения нескольких множеств с использованием трёх вложенных циклов. Количество множеств и их элементов может быть произвольным. Последовательно перемножаем множества и накапливаем результат. Порядок значения не имеет, так как от перестановки множителей произведение не меняется. В результате порядок будет отличаться, но комбинации будут те же самые.
Для наглядности возьмём несколько упорядоченных множеств:
a = [A,B,C,D]
b = [E,F,G]
c = [H,I]
d = [J]
Количество возможных комбинаций — это произведение количеств элементов всех множеств:
4 * 3 * 2 * 1 = 24
Напишем метод на Java для решения подобных задач, будем использовать три вложенных цикла for.
Сначала подготавливаем список списков List<List<T>>, заполненный одним пустым значением.
Будем использовать его как промежуточный результат и как финальный результат.
Затем обходим переданные списки и последовательно дополняем промежуточный результат их элементами. На каждом шаге получаем новый промежуточный результат и двигаемся дальше. Таким образом последовательно перемножаем пары списков и постепенно накапливаем результат.
Схематически этот процесс выглядит следующим образом:
result0: [[]]
list1: [A,B,C,D]
--------
result1: [[A],[B],[C],[D]]
list2: [E,F,G]
--------
result2: [[A,E],[A,F],[A,G],[B,E],[B,F],...[D,G]]
list3: [H,I]
--------
result3: [[A,E,H],[A,E,I],[A,F,H],[A,F,I],[A,G,H],...[D,G,I]]
list4: [J]
--------
result4: [[A,E,H,J],[A,E,I,J],[A,F,H,J],[A,F,I,J],[A,G,H,J],...[D,G,I,J]]
Количество комбинаций: 24
[A, E, H, J] [B, E, H, J] [C, E, H, J] [D, E, H, J]
[A, E, I, J] [B, E, I, J] [C, E, I, J] [D, E, I, J]
[A, F, H, J] [B, F, H, J] [C, F, H, J] [D, F, H, J]
[A, F, I, J] [B, F, I, J] [C, F, I, J] [D, F, I, J]
[A, G, H, J] [B, G, H, J] [C, G, H, J] [D, G, H, J]
[A, G, I, J] [B, G, I, J] [C, G, I, J] [D, G, I, J]
Список может содержать изменяемое количество элементов. Это упрощает код.
/**
* @param lists произвольное количество списков
* @param <T> тип элементов списков
* @return декартово произведение переданных списков
*/
public static <T> List<List<T>> cartesianProduct(List<List<T>> lists) {
// входящие данные не равны null
if (lists == null) return Collections.emptyList();
// промежуточный результат, содержит одно пустое значение
List<List<T>> cp = Collections.singletonList(Collections.<T>emptyList());
// обходим переданные списки
for (List<T> list : lists) {
// ненулевые и непустые списки
if (list == null || list.size() == 0) continue;
// следующий промежуточный результат
List<List<T>> next = new ArrayList<>();
// строки текущего промежуточного результата
for (List<T> row : cp) {
// элементы текущего списка
for (T el : list) {
// новая строка для следующего промежуточного
// результата, копируем текущую строку
List<T> nRow = new ArrayList<>(row);
// добавляем текущий элемент
nRow.add(el);
// помещаем в следующий промежуточный результат
next.add(nRow);
}
}
// обновляем промежуточный результат
cp = next;
}
// возвращаем итоговый результат
return cp;
}
// запускаем программу и выводим результат
public static void main(String[] args) {
// произвольное количество списков и их элементов
List<String> a = Arrays.asList("A", "B", "C", "D");
List<String> b = Arrays.asList("E", "F", "G");
List<String> c = Arrays.asList("H", "I");
List<String> d = Arrays.asList("J");
// декартово произведение
List<List<String>> cp = cartesianProduct(Arrays.asList(a, b, c, d));
// вывод
System.out.println("Количество комбинаций: " + cp.size());
// комбинации по столбцам
int rows = 6;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cp.size(); j++)
if (j % rows == i)
System.out.print(" " + cp.get(j));
System.out.println();
}
}
Вывод для этого и следующего кода одинаковый, см. выше: комбинации по столбцам.
Массив содержит фиксированное количество элементов. Код выглядит немного сложнее.
/**
* @param arrays произвольное количество массивов
* @param clazz класс элементов массивов
* @param <T> тип элементов массивов
* @return декартово произведение переданных массивов
*/
@SuppressWarnings("unchecked")
public static <T> T[][] cartesianProduct(Class<T> clazz, T[]... arrays) {
// входящие данные не равны null
if (clazz == null || arrays == null)
return (T[][]) Array.newInstance(clazz, 0, 0);
// промежуточный результат, содержит одну пустую строку
T[][] cp = (T[][]) Array.newInstance(clazz, 1, 0);
// обходим переданные массивы
for (int a = 0; a < arrays.length; a++) {
// текущий массив
T[] arr = arrays[a];
// ненулевой и непустой массив
if (arr == null || arr.length == 0) continue;
// следующий промежуточный результат, указываем количество строк
T[][] next = (T[][]) Array.newInstance(clazz,cp.length*arr.length,0);
// строки текущего промежуточного результата
for (int r = 0; r < cp.length; r++) {
// текущая строка
T[] row = cp[r];
// элементы текущего массива
for (int e = 0; e < arr.length; e++) {
// текущий элемент
T el = arr[e];
// копируем текущую строку в новый массив [длина + 1]
T[] nRow = Arrays.copyOf(row, row.length + 1);
// добавляем текущий элемент
nRow[row.length] = el;
// помещаем в следующий промежуточный результат
next[r * arr.length + e] = nRow;
}
}
// обновляем промежуточный результат
cp = next;
}
// возвращаем итоговый результат
return cp;
}
// запускаем программу и выводим результат
public static void main(String[] args) {
// произвольное количество массивов и их элементов
String[] a = {"A", "B", "C", "D"};
String[] b = {"E", "F", "G"};
String[] c = {"H", "I"};
String[] d = {"J"};
// декартово произведение
String[][] cp = cartesianProduct(String.class, a, b, c, d);
// вывод
System.out.println("Количество комбинаций: " + cp.length);
// комбинации по столбцам
int rows = 6;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cp.length; j++)
if (j % rows == i)
System.out.print(" " + Arrays.toString(cp[j]));
System.out.println();
}
}
Вывод для этого и предыдущего кода одинаковый, см. выше: комбинации по столбцам.
© Головин Г.Г., Код с комментариями, 2021