Комбинаторика в Python
Комбинаторика — это раздел математики, в котором изучают, сколько комбинаций, подчинённых тем или иным условиям, можно составить из данных объектов. Короче, это все о сочетаниях, перестановках, числе способов и тому подобному.
Почему важна комбинаторика? Нет, не только лишь для решения олимпиадных задач, но также комбинаторика – один из столпов теории вероятностей, которая в свою очередь служит фундаментом для машинного обучения – одно из мощнейших трендов в ПО начале 21-го века!
В встроенном в Python модуле itertools существует ряд комбинаторных функций. Это:
- product() – прямое (Декартово) произведение одного или нескольких итераторов.
- permutations() – перестановки и размещения элементов множества.
- combinations() – уникальные комбинации из элементов множества.
- combinations_with_replacement() – комбинации с замещением (повторами, возвратами).
О каждой из них расскажу подробно. Для начала импортируем все нужные функции из модуля:
Прямое произведение
Прямое, или декартово произведение двух множеств — множество, элементами которого являются все возможные упорядоченные пары элементов исходных множеств. Проще говоря мы берем из первого множества один элемент, а потом из второго выбираем элемент и составляем их в кортеж. Так вот все способы выбрать так элементы – составят декартово произведение. Пример:
>>> A = [1, 2, 3] >>> B = "123" >>> print(*product(A, B)) (1, 'a') (1, 'b') (1, 'c') (2, 'a') (2, 'b') (2, 'c') (3, 'a') (3, 'b') (3, 'c')
Примечания. Во-первых, заметьте, что элементы следуют в строгом лексографическом порядке: сначала берется нулевой элемент из первой последовательности и сочетается с каждым по очереди из второй последовательности. Во-вторых, аргументами функции могут быть любые итерируемые объекты конечной длины. Я взял для примера список и строку, причем строка автоматически разбивается на символы.
В коде произведение множеств эквивалентно вложенным циклам:
>>> print(*[(a, b) for a in A for b in B]) (1, '1') (1, '2') (1, '3') (2, '1') (2, '2') (2, '3') (3, '1') (3, '2') (3, '3')
Результат такой же, но рекомендую использовать именно библиотечную функцию, так как ее реализация, наверняка, будет лучше.
Вы можете передать в функцию больше последовательностей:
>>> print(*product([1, 2, 3])) (1,) (2,) (3,) >>> print(*product([1, 2, 3], [10, 20, 30])) (1, 10) (1, 20) (1, 30) (2, 10) (2, 20) (2, 30) (3, 10) (3, 20) (3, 30) >>> print(*product([1, 2, 3], [10, 20, 30], [100, 200, 300])) (1, 10, 100) (1, 10, 200) (1, 10, 300) (1, 20, 100) (1, 20, 200) (1, 20, 300) (1, 30, 100) (1, 30, 200) (1, 30, 300) (2, 10, 100) (2, 10, 200) (2, 10, 300) (2, 20, 100) (2, 20, 200) (2, 20, 300) (2, 30, 100) (2, 30, 200) (2, 30, 300) (3, 10, 100) (3, 10, 200) (3, 10, 300) (3, 20, 100) (3, 20, 200) (3, 20, 300) (3, 30, 100) (3, 30, 200) (3, 30, 300)
Каждый выходной элемент будет кортежем (даже в случае, если в нем только один элемент!). Также обратите внимание на то, что функция product (как и все остальные из сегодняшнего набора) возвращает не список, а особый ленивый объект. Чтобы получить все элементы, нужно преобразовать его в список функцией list:
>>> product([1, 2, 3], 'abc') >>> list(product([1, 2, 3], 'abc')) [(1, 'a'), (1, 'b'), (1, 'c'), (2, 'a'), (2, 'b'), (2, 'c'), (3, 'a'), (3, 'b'), (3, 'c')]
Количество элементов на выходе будет произведением длин всех последовательностей на входе:
В функцию product можно передать именованный параметр repeat, который указывает сколько раз повторять цепочку вложенных циклов (по умолчанию один раз). Если repeat >= 2, то это называют декартовой степенью. То есть множество умножается на себя несколько раз. Так при repeat=2 эквивалентным кодом будет:
>>> [(a, b, a1, b1) for a in A for b in B for a1 in A for b1 in B] == list(product(A, B, repeat=2)) True
В таком случае количество элементов в результате будет вычисляться по схожей формуле с учетом того, что каждый множитель будет в степени repeat:
» width=»412″ height=»43″/>
Перестановки
Функция permutations возвращает последовательные перестановки элементов входного множества. Первый элемент – будет исходным множеством. Второй – результат перестановки какой-то пары элементов и так далее, пока не будут перебраны все уникальные комбинации. Уникальность здесь рассматривается по позициям элементов в исходной последовательности, а не по и их значению, то есть элементы между собой алгоритмом не сравниваются. Важны только их индексы.
Число объектов остается неизменными, меняется только их порядок.
>>> print(*permutations("ABC")) ('A', 'B', 'C') ('A', 'C', 'B') ('B', 'A', 'C') ('B', 'C', 'A') ('C', 'A', 'B') ('C', 'B', 'A')
Например размещения для двух элементов из коллекции из трех элементов:
>>> print(*permutations("ABC", 2)) ('A', 'B') ('A', 'C') ('B', 'A') ('B', 'C') ('C', 'A') ('C', 'B') # 2 из 4 >>> print(*permutations([1, 2, 3, 4], 2)) (1, 2) (1, 3) (1, 4) (2, 1) (2, 3) (2, 4) (3, 1) (3, 2) (3, 4) (4, 1) (4, 2) (4, 3)
Количество вариантов получится по формуле (n – длина исходной последовательности):