Комбинации с повторениями

Этот пример демонстрирует генерацию комбинаций с повторениями из списка элементов, используя библиотеку Combinatorics в Julia.

Введение

Алгоритм "комбинации с повторениями" позволяет получать все возможные подмножества заданного размера, где элементы могут повторяться. Это полезно, например, при подсчёте количества способов выбрать предметы, если можно выбирать один и тот же предмет несколько раз (например, выбрать 2 пирожка из нескольки видов пирожков).

Такой подход применяется в комбинаторике и задачах теории вероятностей.

# Если пакет Combinatorics ещё не установлен, выполним строку:
import Pkg; Pkg.add("Combinatorics")

# Импорт библиотеки Combinatorics для работы с комбинаторными функциями
using Combinatorics

Пример использования с массивом строк

Создаём список строк и выводим его содержание. Далее генерируем все возможные комбинации с повторениями длины 2. Такие комбинации также называют "multicombinations"

# Определяем массив строк — это будут наши исходные элементы
l = ["капуста", "картошка", "повидло"] # Виды пирожков

# Печать заголовков
println("Список: ", l)
println("Комбинации:")

# Проходим по всем комбинациям с повторениями длины 2
for c in with_replacement_combinations(l, 2)
    println(c) # Выводим каждую комбинацию
end

Список: ["капуста", "картошка", "повидло"]
Комбинации:
["капуста", "капуста"]
["капуста", "картошка"]
["капуста", "повидло"]
["картошка", "картошка"]
["картошка", "повидло"]
["повидло", "повидло"]

Подсчёт числа комбинаций

Функция with_replacement_combinations() может работать и с ranges (диапазонами). Мы считаем количество трёхэлементных комбинаций с повторениями из чисел от 1 до 10. Это соответствует формуле сочетаний с повторениями:

где – число различных элементов,

– размер комбинации.

Для и будет .

# Вычисляем общее количество трёхэлементных комбинаций с повторениями из диапазона 1..10
length_combs = length(with_replacement_combinations(1:10, 3))

220

Заключение

Мы рассмотрели использование библиотеки Combinatorics в языке программирования Julia для генерации комбинаций с повторениями. Создали пример со списком названий пирожков, вывели все возможные пары с повторами, а также подсчитали общее количество таких троек среди целых чисел от 1 до 10.

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

Пример разработан с использованием материалов Rosetta Code

Комбинации с повторениями