Создание комбинаций в Java

19 января 2022 г. · 8 мин. чтения

1. Введение

В этом уроке мы обсудим решение проблемы k-комбинаций в Java .

Во-первых, мы обсудим и реализуем как рекурсивные, так и итеративные алгоритмы для генерации всех комбинаций заданного размера. Затем мы рассмотрим решения с использованием распространенных библиотек Java.

2. Обзор комбинаций

Проще говоря, комбинация — это подмножество элементов из заданного множества .

В отличие от перестановок, порядок, в котором мы выбираем отдельные элементы, не имеет значения. Вместо этого нас заботит только то, находится ли конкретный элемент в выборе.

Например, в карточной игре нам нужно раздать 5 карт из колоды, состоящей из 52 карт. Нас не интересует порядок, в котором были выбраны 5 карт. Скорее, нас волнует только то, какие карты присутствуют в руке.

Некоторые задачи требуют от нас оценки всех возможных комбинаций. Для этого перечислим различные комбинации.

Количество различных способов выбора «r» элементов из набора «n» элементов может быть выражено математически с помощью следующей формулы:

./b7fa9c5b4fb6e17dc08f8ecc8c0ce88f.png

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

В таких случаях мы можем случайным образом выбрать несколько репрезентативных выборок. Процесс называется выборкой .

Далее мы рассмотрим различные алгоритмы составления списка комбинаций.

3. Рекурсивные алгоритмы для генерации комбинаций

Рекурсивные алгоритмы обычно работают, разбивая проблему на аналогичные более мелкие задачи. Этот процесс продолжается до тех пор, пока мы не достигнем условия завершения, что также является базовым случаем. Затем мы решаем базовый случай напрямую.

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

3.1. Разбиение по элементам всего набора

Разделим задачу выбора « r» элементов из « n» элементов, просматривая элементы один за другим. Для каждого элемента в наборе мы можем либо включить его в выборку, либо исключить.

Если мы включаем первый элемент, то нам нужно выбрать «r — 1» элементов из оставшихся « n — 1» элементов . С другой стороны, если мы отбросим первый элемент, то нам нужно выбрать « r» элементов из оставшихся « n — 1» элементов.

Это может быть математически выражено как:

./1a39c11a5ca2a155b0a0037dfa52ce52.png

Теперь давайте рассмотрим рекурсивную реализацию этого подхода:

private void helper(List<int[]> combinations, int data[], int start, int end, int index) {
    if (index == data.length) {
        int[] combination = data.clone();
        combinations.add(combination);
    } else if (start <= end) {
        data[index] = start;
        helper(combinations, data, start + 1, end, index + 1);
        helper(combinations, data, start + 1, end, index);
    }
}

Вспомогательный метод делает два рекурсивных вызова самого себя . Первый вызов включает текущий элемент. Второй вызов отбрасывает текущий элемент.

Далее давайте напишем генератор комбинаций, используя этот вспомогательный метод:

public List<int[]> generate(int n, int r) {
    List<int[]> combinations = new ArrayList<>();
    helper(combinations, new int[r], 0, n-1, 0);
    return combinations;
}

В приведенном выше коде метод generate устанавливает первый вызов вспомогательного метода и передает соответствующие параметры.

Далее вызовем этот метод для генерации комбинаций:

List<int[]> combinations = generate(N, R);
for (int[] combination : combinations) {
    System.out.println(Arrays.toString(combination));
}
System.out.printf("generated %d combinations of %d items from %d ", combinations.size(), R, N);

При выполнении программы мы получаем следующий вывод:

[0, 1]
[0, 2]
[0, 3]
[0, 4]
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
generated 10 combinations of 2 items from 5

Наконец, давайте напишем тестовый пример:

@Test
public void givenSetAndSelectionSize_whenCalculatedUsingSetRecursiveAlgorithm_thenExpectedCount() {
    SetRecursiveCombinationGenerator generator = new SetRecursiveCombinationGenerator();
    List<int[]> selection = generator.generate(N, R);
    assertEquals(nCr, selection.size());
}

Легко заметить, что требуемый размер стека равен количеству элементов в наборе. Когда количество элементов в наборе велико, например, превышает максимальную глубину стека вызовов, мы переполним стек и получим StackOverflowError .

Следовательно, этот подход не работает, если входной набор велик.

3.2. Разделение по элементам в комбинации

Вместо отслеживания элементов входного набора мы разделим задачу, отслеживая элементы в выборке .

Во-первых, давайте упорядочим элементы во входном наборе, используя индексы от «1» до « n» . Теперь мы можем выбрать первый элемент из первых « n-r+1» .

Предположим, что мы выбрали k -й элемент. Затем нам нужно выбрать « r — 1» элементов из оставшихся « n — k» элементов, проиндексированных от « k + 1» до « n» .

Выразим этот процесс математически как:

Далее давайте напишем рекурсивный метод для реализации этого подхода:

private void helper(List<int[]> combinations, int data[], int start, int end, int index) {
    if (index == data.length) {
        int[] combination = data.clone();
        combinations.add(combination);
    } else {
        int max = Math.min(end, end + 1 - data.length + index);
        for (int i = start; i <= max; i++) {
            data[index] = i;
            helper(combinations, data, i + 1, end, index + 1);
        }
    }
}

В приведенном выше коде цикл for выбирает следующий элемент, а затем рекурсивно вызывает метод helper() для выбора оставшихся элементов . Останавливаемся, когда выбрано необходимое количество предметов.

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

public List<int[]> generate(int n, int r) {
    List<int[]> combinations = new ArrayList<>();
    helper(combinations, new int[r], 0, n - 1, 0);
    return combinations;
}

Наконец, давайте напишем тестовый пример:

@Test
public void givenSetAndSelectionSize_whenCalculatedUsingSelectionRecursiveAlgorithm_thenExpectedCount() {
    SelectionRecursiveCombinationGenerator generator = new SelectionRecursiveCombinationGenerator();
    List<int[]> selection = generator.generate(N, R);
    assertEquals(nCr, selection.size());
}

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

Если количество выбираемых элементов также велико, этот метод не сработает.

4. Итерационный алгоритм

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

Сгенерируем комбинации в лексикографическом порядке. Начнем с самой низкой лексикографической комбинации.

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

Давайте напишем код, который следует этому подходу:

public List<int[]> generate(int n, int r) {
    List<int[]> combinations = new ArrayList<>();
    int[] combination = new int[r];

    // initialize with lowest lexicographic combination
    for (int i = 0; i < r; i++) {
        combination[i] = i;
    }

    while (combination[r - 1] < n) {
        combinations.add(combination.clone());

         // generate next combination in lexicographic order
        int t = r - 1;
        while (t != 0 && combination[t] == n - r + t) {
            t--;
        }
        combination[t]++;
        for (int i = t + 1; i < r; i++) {
            combination[i] = combination[i - 1] + 1;
        }
    }

    return combinations;
}

Далее напишем тестовый пример:

@Test
public void givenSetAndSelectionSize_whenCalculatedUsingIterativeAlgorithm_thenExpectedCount() {
    IterativeCombinationGenerator generator = new IterativeCombinationGenerator();
    List<int[]> selection = generator.generate(N, R);
    assertEquals(nCr, selection.size());
}

Теперь давайте воспользуемся некоторыми библиотеками Java для решения проблемы.

5. Библиотеки Java, реализующие комбинации

Насколько это возможно, мы должны повторно использовать существующие реализации библиотек вместо развертывания собственных. В этом разделе мы рассмотрим следующие библиотеки Java, реализующие комбинации:

Апач Коммонс
Гуава
КомбинаторикаLib

5.1. Апач Коммонс

Класс CombinatoricsUtils из Apache Commons предоставляет множество комбинированных служебных функций. В частности, методcombinationsIterator возвращает итератор, который будет генерировать комбинации в лексикографическом порядке.

Во-первых, давайте добавим в проект зависимости Maven commons-math3 :

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-math3</artifactId>
    <version>3.6.1</version>
</dependency>

Далее, давайте воспользуемся методомcombinationsIterator для печати комбинаций :

public static void generate(int n, int r) {
    Iterator<int[]> iterator = CombinatoricsUtils.combinationsIterator(n, r);
    while (iterator.hasNext()) {
        final int[] combination = iterator.next();
        System.out.println(Arrays.toString(combination));
    }
}

5.2. Google Гуава

Класс Sets из библиотеки Guava предоставляет служебные методы для операций, связанных с множествами. Метод комбинаций возвращает все подмножества заданного размера .

Во-первых, давайте добавим в проект зависимость maven для библиотеки Guava :

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.0.1-jre</version>
</dependency>

Далее, давайте воспользуемся методом комбинаций для генерации комбинаций :

Set<Set<Integer>> combinations = Sets.combinations(ImmutableSet.of(0, 1, 2, 3, 4, 5), 3);

Здесь мы используем метод ImmutableSet.of для создания набора из заданных чисел.

5.3. КомбинаторикаLib

CombinatoricsLib — это небольшая и простая библиотека Java для перестановок, комбинаций, подмножеств, целочисленных разделов и декартовых произведений.

Чтобы использовать его в проекте, добавим Maven-зависимость combinatoricslib3 :

<dependency>
    <groupId>com.github.dpaukov</groupId>
    <artifactId>combinatoricslib3</artifactId>
    <version>3.3.0</version>
</dependency>

Далее воспользуемся библиотекой для печати комбинаций:

Generator.combination(0, 1, 2, 3, 4, 5)
  .simple(3)
  .stream()
  .forEach(System.out::println);

Это производит следующий вывод при выполнении:

[0, 1, 2]
[0, 1, 3]
[0, 1, 4]
[0, 1, 5]
[0, 2, 3]
[0, 2, 4]
[0, 2, 5]
[0, 3, 4]
[0, 3, 5]
[0, 4, 5]
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]

Дополнительные примеры доступны по адресу combinatoricslib3-example .

6. Заключение

В этой статье мы реализовали несколько алгоритмов для генерации комбинаций.

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

Как обычно, полный исходный код можно найти на GitHub .

1. Введение​

2. Обзор комбинаций​

3. Рекурсивные алгоритмы для генерации комбинаций​

3.1. Разбиение по элементам всего набора​

3.2. Разделение по элементам в комбинации​

4. Итерационный алгоритм​

5. Библиотеки Java, реализующие комбинации​

5.1. Апач Коммонс​

5.2. Google Гуава​

5.3. КомбинаторикаLib​

6. Заключение​