Combinations with repetitions

This example demonstrates generating combinations with repetitions from a list of items using the library Combinatorics in Julia.

Introduction

The "combination with repetitions" algorithm allows you to obtain all possible subsets of a given size, where elements can be repeated. This is useful, for example, when calculating the number of ways to select items, if you can select the same item several times (for example, choose 2 pies from several types of pies).

This approach is used in combinatorics and probability theory problems.

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

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

An example of using it with an array of strings

Creating a list of lines and displaying its contents. Next, we generate all possible combinations with repetitions of length 2. Such combinations are also called "multicombinations"

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

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

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

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

Counting the number of combinations

Function with_replacement_combinations() It can also work with ranges (ranges). We count the number of three-element combinations with repetitions of numbers from 1 to 10. This corresponds to the formula of combinations with repetitions:

where – the number of different elements,

– the size of the combination.

For and will be .

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

220

Conclusion

We have reviewed the use of the library Combinatorics in the Julia programming language for generating combinations with repetitions. We created an example with a list of pie names, displayed all possible pairs with repetitions, and calculated the total number of such triples among the integers from 1 to 10.

This allows you to efficiently perform combinatorial calculations without having to implement algorithms yourself.

The example was developed using materials from Rosetta Code