Комбинаторика – раздел математики, где ставится вопрос о подсчете числа вариантов выбора элементов из некоторого множества согласно определенным правилам.

В задании №8 в ЕГЭ по информатике присутствуют задачи по теме "Комбинаторика", которые могут быть решены как с помощью формул, так и средствами программирования. Как правило, на динамическое программирование задачи в данном задании отсутствуют. Используя сразу два метода при решении задачи, можно с высокой долей вероятности гарантировать получение верного ответа в случае его совпадения в обоих решениях.

Далее рассмотрим основные понятия и формулы по данной теме.

Размещение

Размещение – упорядоченный набор из k различных элементов некоторого n-элементного множества.

${\stackrel{}{A}}_n^k\mathit{=}\frac{n\mathit{!}}{\mathit{(}n\mathit{-}k\mathit{)}\mathit{!}}$

Размещение с повторением

Размещение с повторением – упорядоченный набор из k элементов некоторого n-элементного множества.

${\stackrel{‾‾‾}{A}}_n^k\mathit{=}{n}^k$

Перестановка

Перестановка – последовательность и n различных элементов.

$P_n=n!$

Перестановка с повторением

Перестановка с повторением – последовательность, содержащая n элементов из k типов.

$P(n_1,n_2,...,n_k)=\frac{n!}{n_1!\cdot n_2!\cdot ...{\cdot n}_k!}$

$\underset{n_1}{\underbrace{\mathrm{aa...a}}}\underset{n_2}{\underbrace{\mathrm{bb...b}}}...\underset{n_k}{\underbrace{\mathrm{xx...x}}}$

Сочетание

Сочетанием из n элементов по k называются подмножества содержащие k элементов из n.

$C_n^k=\frac{n\mathit{!}}{k\mathit{!}\cdot (n-k)\mathit{!}}$

Следует также упомянуть ряд полезных формул с сочетаниями:

$C_n^k=C_n^{n-k}$

$C_n^k=C_{n-\mathit{1}}^{k-\mathit{1}}+C_{n-\mathit{1}}^k$

$C_n^{\mathit{0}}+C_n^{\mathit{1}}+\mathit{...}+C_n^n={\mathit{2}}^n$

${(x+y)}^n=C_n^{\mathit{0}}\cdot x^n\cdot y^{\mathit{0}}+\mathit{...}+C_n^k\cdot x^{n-k}\cdot y^k+\mathit{...}+C_n^n\cdot x^{\mathit{0}}\cdot y^n$

Сочетание с повторением

Сочетанием с повторением называются наборы из k элементов n - элементного множества, возможно с повторяющимися элементами. Порядок элементов не учитывается.

${\stackrel{‾‾‾}{C}}_n^k=C_{\mathrm{n+k-1}}^k=\frac{(n+k-\mathit{1})\mathit{!}}{k\mathit{!}\cdot (n-k)\mathit{!}}$

Вычисление факториала и сочетаний в Python

Самостоятельная реализация:

#вычисление факториала def f(n): res = 1 for i in range(2, n+1): res *= i return res #вычисление числа сочетаний def c(k, n): return f(n) // f(k) // f(n-k) print(f(5)) # 120 print(c(2, 5)) # 10

Реализация с использованием библиотеки math:

from math import * print(factorial(5)) # 120 print(comb(5, 2)) # 10

Генерация комбинаторных списков в Python

Библиотека itertools языка Python содержит функции, позволяющие генерировать комбинаторные списки:

from itertools import * #декартово произведение l1 = product("AB", [1, 2]) print(list(l1)) #[('A', 1), ('A', 2), ('B', 1), ('B', 2)] #перестановки l2 = permutations([1, 2, 3]) print(list(l2)) #[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)] #сочетания l3 = combinations("ABCD", 2) print(list(l3)) #[('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('C', 'D')] #сочетания c повторениями l4 = combinations_with_replacement("ABC", 2) print(list(l4)) #[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]

Далее, более детально разберем приведенные выше генераторы:

Декартово произведение (product)

Декартово произведение множества X и множества Y – это множество, содержащее все упорядоченные пары (x, y), в которых x принадлежит множеству X, а y принадлежит множеству Y.

Чтобы вычислить произведение итерируемого объекта умноженного самого на себя, в объекте product можно указать число повторений с помощью параметра repeat.

Например,  product(A, repeat=4) – тоже самое, что и product(A, A, A, A).

tertools.product(*iterables, repeat)

from itertools import * l1 = product("ABC", [1, 2]) print(list(l1)) #[('A', 1), ('A', 2), ('B', 1), ('B', 2), ('C', 1), ('C', 2)] l2 = product("xy", repeat=2) print(list(l2)) #[('x', 'x'), ('x', 'y'), ('y', 'x'), ('y', 'y')] l3 = product("aa", repeat=2) print(list(l3)) #[('a', 'a'), ('a', 'a'), ('a', 'a'), ('a', 'a')] l4 = product([1, 2], [3, 4], [5, 6]) print(list(l4)) #[(1, 3, 5), (1, 3, 6), (1, 4, 5), (1, 4, 6), (2, 3, 5), (2, 3, 6), (2, 4, 5), (2, 4, 6)]

Перестановки (permutations)

Объект permutation возвращает последовательные перестановки элементов в итерируемом объекте. Кортежи перестановок выдаются в лексикографическим порядке в соответствии с порядком итерации входных данных. Таким образом, если входные данные итерируемого объекта отсортированы, то комбинация кортежей будет выдаваться в отсортированном порядке. Параметр r определяет вывод размещений из заданного числа элементов (None = все).

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

itertools.permutations(iterable, r=None)

from itertools import * l1 = permutations("ABC") print(list(l1)) #[('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')] l2 = permutations([3, 2, 1]) print(list(l2)) #[(3, 2, 1), (3, 1, 2), (2, 3, 1), (2, 1, 3), (1, 3, 2), (1, 2, 3)] l3 = permutations([1, 2, 3, 4], 2) print(list(l3)) #[(1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,3)]

Сочетания (combinations)

Объект combinations возвращает подпоследовательности длины r из элементов итерируемого объекта, подаваемого на вход.  При этом параметр r не может быть опущен.

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

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

itertools.combinations(iterable, r)

from itertools import * l1 = combinations("ABCD", 2) print(list(l1)) #[('A','B'), ('A','C'), ('A','D'), ('B','C'), ('B','D'), ('C','D')] l2 = combinations([4, 3, 2, 1], 3) print(list(l2)) #[(4, 3, 2), (4, 3, 1), (4, 2, 1), (3, 2, 1)]

Сочетания с повторениями (combinations_with_replacement)

Объект combinations_with_replacement возвращает подпоследовательности длины r из элементов итерируемого объекта, подаваемого на вход, при этом отдельные элементы могут повторяться больше одного раза. 

itertools.combinations_with_replacement(iterable, r)

Приведем пример использования данного итератора в совокупности с сочетаниями  без повторений и декартовым произведением на сходных входных данных для лучше представления:

from itertools import * l1 = combinations("ABC", 2) print(list(l1)) #[('A', 'B'), ('A', 'C'), ('B', 'C')] l2 = product("ABC", repeat=2) print(list(l2)) #[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'C')] l3 = combinations_with_replacement("ABC", 2) print(list(l3)) #[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]