Декартово произведение множеств python

Комбинаторика в 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 – длина исходной последовательности):

combinations – функция, коротая выбирает все сочетания из входной последовательности. Пусть в ней имеется n различных объектов. Будем выбирать из них r объектов всевозможными способами (то есть меняется состав выбранных объектов, но порядок не важен). Получившиеся комбинации называются сочетаниями из n объектов по r, а их число равно:

Функция combinations_with_replacement описывает, сколькими способами можно составить комбинацию по r элементов из элементов n типов (элементы в комбинации могут повторяться, но порядок их не важен). Обратите внимание на слово « тип «, в простых сочетаниях элементы не повторялись внутри одной выборки, они были как бы конкретными экземплярами.

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

>>> print(*combinations_with_replacement(['red', 'white', 'black'], 2)) ('red', 'red') ('red', 'white') ('red', 'black') ('white', 'white') ('white', 'black') ('black', 'black')

Поэтому, имея возможность брать один и тот же элемент несколько раз, можно выбрать из последовательности в три элемента 4, и 5, и сколь угодно много (больше, чем было исходных типов). Например, по 4 из 2:

>>> print(*combinations_with_replacement(['red', 'black'], 4)) ('red', 'red', 'red', 'red') ('red', 'red', 'red', 'black') ('red', 'red', 'black', 'black') ('red', 'black', 'black', 'black') ('black', 'black', 'black', 'black')

Вот графически сочетания с повторами по 2 из 3:

Формула числа элементов на выходе такова:

def decart(s1,s2): return [(a,b) for a in s1 for b in s2]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

import itertools def pr(mstr, mstr1): mstet = set(mstr) mstet1 = set(mstr1) print(mstet) print(mstet1) for element in itertools.product(*mstet,*mstet1): print(element) if __name__ == '__main__': mstr = input() mstr1 = input() pr(mstr, mstr1)