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

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

Задача о сервировке стола • Метод для решения на Java

Размещением называется упорядоченный набор {k} различных элементов из множества {n} различных элементов, где {k ≤ n}. Если {k = n}, то такой упорядоченный набор называется перестановкой. Для универсальности решения перестановки тоже будем учитывать как частный случай размещения.

Количество возможных комбинаций #

Для наглядности возьмём последовательность из трёх элементов {XYZ}, нарисуем все возможные подмножества этого множества, добавим к ним перестановки и подсчитаем количество комбинаций.

Получаем количество всех возможных размещений элементов последовательности

Формула количества размещений:

$\sum_{k=0}^{n} {n! \over (n-k)!}$

Последовательность из трёх элементов:

$\sum_{k=0}^{3} {3! \over (3-k)!} = {3! \over 3!} + {3! \over 2!} + {3! \over 1!} + {3! \over 0!} = 1+3+6+6 = 16.$

Способ реализации на Java:

public static void main(String[] args) {
    // количество элементов последовательности
    int n = 3;
    // количество возможных комбинаций
    int sum = 0;
    // обходим возможные количества элементов
    for (int k = 0; k <= n; k++)
        // складываем количества размещений
        sum += factorial(n) / factorial(n - k);
    // вывод
    System.out.println(sum); // 16
}
// получаем факториал числа
static int factorial(int n) {
    int fact = 1;
    for (int i = 2; i <= n; i++)
        fact *= i;
    return fact;
}

Комбинации из трёх элементов #

Сравним две последовательности из трёх элементов: цифр {123} и букв {XYZ}. Тип элементов разный — комбинации одинаковые, потому что порядковые номера у элементов те же самые.

Количество вариантов: 16
[][1][2][3][12][13][21][23][31][32][123][132][213][231][312][321]
[][X][Y][Z][XY][XZ][YX][YZ][ZX][ZY][XYZ][XZY][YXZ][YZX][ZXY][ZYX]

Сравним последовательности из [1..12] элементов: количество вариантов быстро растёт и вскоре выходит за пределы Integer, далее при {n > 12} нужно будет использовать Long, а при {n > 20} — уже BigInteger.

n Кол-во вариантов
1 2
2 5
3 16
4 65
5 326
6 1957
7 13700
8 109601
9 986410
10 9864101
11 108505112
12 1302061345

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

Задача о сервировке стола #

На ужин приглашено четверо гостей {n = 4}, из которых известно, что приедут не более двух человек {k = 2}, причём порядок их появления важен, поскольку от этого зависит сервировка стола. Известно также, что когда приедет первый, то он скажет, кто будет второй и приедет ли он. Рассчитать возможные варианты сервировки стола.

Способ решения #

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

static List<Set<Integer>> combinationsOfElements(int size, int min, int max)

Вызываем метод с отбором {min=0; max=2} и получаем список комбинаций указанной длины.

// задача о сервировке стола
public static void main(String[] args) {
    // приглашено четверо гостей
    int[] arr = {1, 2, 3, 4};
    // n - количество элементов последовательности
    // k - максимальное количество элементов в комбинации
    int n = 4, k = 2;
    // комбинации элементов указанной длины [0..2]
    List<Set<Integer>> list = combinationsOfElements(n, 0, k);
    // вывод
    System.out.println("Количество вариантов: " + list.size());
    for (Set<Integer> set : list) {
        System.out.print("[");
        for (int i : set)
            System.out.print(arr[i]);
        System.out.print("]");
    }
}

Вывод:

Количество вариантов: 17
[][1][2][3][4][12][13][14][21][23][24][31][32][34][41][42][43]

Комбинации элементов указанной длины #

Пишем метод на Java с использованием трёх вложенных циклов for. Далее для проверки вызываем этот метод без отбора {min=0; max=size} и получаем все возможные комбинации. Для примера возьмём две последовательности из трёх элементов: цифр {123} и букв {XYZ}.

Описание метода #

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

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

/**
 * @param size размер последовательности (0 ≤ min ≤ max ≤ size)
 * @param min  минимальное количество элементов в комбинации
 * @param max  максимальное количество элементов в комбинации
 * @return комбинации элементов указанной длины
 */
static List<Set<Integer>> combinationsOfElements(int size, int min, int max) {
    // некорректные входящие данные, возвращаем пустой список комбинаций
    if (0 > min || min > max || max > size) return Collections.emptyList();
    // результирующий список комбинаций
    List<Set<Integer>> result = new ArrayList<>();
    // текущий список комбинаций, количество элементов во всех
    // комбинациях одинаковое, начинаем с одной пустой комбинации
    List<Set<Integer>> sublist = Arrays.asList(Collections.<Integer>emptySet());
    // обходим возможные количества элементов в комбинации
    for (int l = 0; l < Math.min(size, max); l++) {
        // если текущее количество элементов входит в отбор,
        // тогда добавляем эти комбинации к результату
        if (l >= min) result.addAll(sublist);
        // следующий список комбинаций
        List<Set<Integer>> nSublist = new ArrayList<>();
        // обходим текущий список комбинаций
        for (Set<Integer> comb : sublist) {
            // обходим индексы элементов последовательности
            for (int i = 0; i < size; i++) {
                // пропускаем те индексы, которые уже есть
                if (comb.contains(i)) continue;
                // новая комбинация, копируем текущую
                Set<Integer> nComb = new LinkedHashSet<>(comb);
                // добавляем текущий индекс
                nComb.add(i);
                // помещаем в новый список комбинаций
                nSublist.add(nComb);
            }
        }
        // обновляем текущий список комбинаций
        sublist = nSublist;
    }
    // добавляем текущий список комбинаций к результату
    result.addAll(sublist);
    // возвращаем результат
    return result;
}

// запускаем программу и выводим результат
public static void main(String[] args) {
    // две последовательности из трёх элементов
    Integer[] arr1 = {1, 2, 3};
    String[] arr2 = {"X", "Y", "Z"};
    // количество элементов последовательности
    int n = 3;
    // все возможные комбинации элементов [0..n]
    List<Set<Integer>> list = combinationsOfElements(n, 0, n);
    // вывод
    System.out.println("Количество вариантов: " + list.size());
    for (Object[] arr : Arrays.asList(arr1, arr2)) {
        StringBuilder sb = new StringBuilder();
        for (Set<Integer> set : list) {
            sb.append("[");
            for (int i : set) sb.append(arr[i]);
            sb.append("]");
        }
        System.out.println(sb);
    }
}

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