Комбинации элементов по столбцам

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

13.09.2021

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

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

     | col1 | col2 | col3 | col4
-----|------|------|------|------
row1 | "A1" | "B1" | "C1" | "D1"
row2 | "A2" | "B2" | null | "D2"
row3 | "A3" | null | null | "D3"
row4 | "A4" | null |

Количество возможных комбинаций — это произведение количеств элементов во всех колонках:

4 * 2 * 1 * 3 = 24

Напишем метод на Java для решения подобных задач, будем использовать три вложенных цикла for.

Сначала подготавливаем список списков List<List<T>>, заполненный одним пустым значением. Будем использовать его как промежуточный результат и как финальный результат.

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

Схематически этот процесс выглядит следующим образом:

res0 * col1 = res1 * col2 = res2  * col3 = res3     * col4 = res4
-----|------|------|------|-------|------|----------|------|------------
[]   * A1   = A1   * B1   = A1,B1 * C1   = A1,B1,C1 * D1   = A1,B1,C1,D1
     * A2   = A2   * B2   = A1,B2 *      = A1,B2,C1 * D2   = A1,B1,C1,D2
     * A3   = A3   *      = A2,B1 *      = A2,B1,C1 * D3   = A1,B1,C1,D3
     * A4   = A4   *      = A2,B2 *      = A2,B2,C1 *      = A1,B2,C1,D1
     *      =      *      = A3,B1 *      = A3,B1,C1 *      = A1,B2,C1,D2
     *      =      *      = A3,B2 *      = A3,B2,C1 *      = A1,B2,C1,D3
     *      =      *      = A4,B1 *      = A4,B1,C1 *      = A2,B1,C1,D1
     *      =      *      = A4,B2 *      = A4,B2,C1 *      = A2,B1,C1,D2
     *      =      *      =       *      =          *      = A2,B1,C1,D3
     *      =      *      =       *      =          *      = A2,B2,C1,D1
     *      =      *      =       *      =          *      = ...........
     *      =      *      =       *      =          *      = ...........
     *      =      *      =       *      =          *      = A4,B2,C1,D3
-----|------|------|------|-------|------|----------|------|------------
1    * 4    = 4    * 2    = 8     * 1    = 8        * 3    = 24

Комбинации по столбцам #

Количество комбинаций: 24
 [A1, B1, C1, D1] [A2, B1, C1, D1] [A3, B1, C1, D1] [A4, B1, C1, D1]
 [A1, B1, C1, D2] [A2, B1, C1, D2] [A3, B1, C1, D2] [A4, B1, C1, D2]
 [A1, B1, C1, D3] [A2, B1, C1, D3] [A3, B1, C1, D3] [A4, B1, C1, D3]
 [A1, B2, C1, D1] [A2, B2, C1, D1] [A3, B2, C1, D1] [A4, B2, C1, D1]
 [A1, B2, C1, D2] [A2, B2, C1, D2] [A3, B2, C1, D2] [A4, B2, C1, D2]
 [A1, B2, C1, D3] [A2, B2, C1, D3] [A3, B2, C1, D3] [A4, B2, C1, D3]

Декартово произведение по столбцам #

Код будет выглядеть проще, если предварительно транспонировать массив массивов, но если этого нельзя сделать, тогда во внешнем цикле обходим колонки массива до тех пор, пока они ещё есть.

/**
 * @param table двухмерный список
 * @param <T>   тип элементов списка
 * @return декартово произведение элементов по столбцам
 */
public static <T> List<List<T>> cartesianProduct(List<List<T>> table) {
    // входящие данные не равны null
    if (table == null) return Collections.emptyList();
    // промежуточный результат, содержит одно пустое значение
    List<List<T>> cp = Collections.singletonList(Collections.<T>emptyList());
    // колонки ещё есть
    boolean notLast = true;
    // обходим колонки таблицы, пока они ещё есть
    for (int i = 0; notLast; i++) {
        // колонок больше нет
        notLast = false;
        // следующий промежуточный результат
        List<List<T>> next = new ArrayList<>();
        // обходим комбинации текущего промежуточного результата
        for (List<T> comb : cp) {
            // обходим строки таблицы
            for (List<T> row : table) {
                // если колонка ещё есть и значение в ней тоже есть
                if (row != null && i < row.size() && row.get(i) != null) {
                    // новая комбинация, копируем текущую комбинацию
                    List<T> nComb = new ArrayList<>(comb);
                    // добавляем значение из колонки
                    nComb.add(row.get(i));
                    // помещаем в новый промежуточный результат
                    next.add(nComb);
                    // колонки ещё есть
                    notLast = true;
                }
            }
        }
        // если колонки ещё есть, то обновляем промежуточный результат
        // и переходим на следующую итерацию, иначе выходим из цикла
        if (notLast) cp = next;
    }
    // возвращаем итоговый результат
    return cp;
}

// запускаем программу и выводим результат
public static void main(String[] args) {
    // произвольное количество строк и их элементов
    List<String> row1 = Arrays.asList("A1", "B1", "C1", "D1");
    List<String> row2 = Arrays.asList("A2", "B2", null, "D2");
    List<String> row3 = Arrays.asList("A3", null, null, "D3");
    List<String> row4 = Arrays.asList("A4", null);
    // зубчатый двухмерный список
    List<List<String>> table = Arrays.asList(row1, row2, row3, row4);
    // декартово произведение
    List<List<String>> cp = cartesianProduct(table);
    // вывод
    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();
    }
}

Вывод для этого кода см. выше: комбинации по столбцам.