ГЛАВНАЯ RU typewriter

older-tomato

Декартово произведение множеств

Комбинаторика • Прямое произведение 06.09.2021

Рассмотрим алгоритм получения декартова произведения нескольких множеств с использованием трёх вложенных циклов. Количество множеств и их элементов может быть произвольным. Последовательно перемножаем множества и накапливаем результат. Порядок значения не имеет, так как от перестановки множителей произведение не меняется. В результате порядок будет отличаться, но комбинации будут те же самые.

Для наглядности возьмём несколько упорядоченных множеств:

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