Введение
При решении комбинаторных задач мы часто сталкиваемся с необходимостью перебирать различные комбинации элементов: генерировать все возможные пароли заданной длины, составлять кодовые слова из определённого алфавита или находить все перестановки символов. Написание подобного функционала вручную требует времени и чревато ошибками, особенно когда условия задачи усложняются.
К счастью, Python предлагает очень удобное решение этой проблемы — встроенный модуль itertools. Этот модуль содержит набор функций для эффективной работы с итераторами и позволяет решать комбинаторные задачи буквально в несколько строк кода.
Углубляться в работу с итераторами мы особо не будем. И в данной статье посвятим себя двум наиболее полезным функциям этого модуля: product() и permutations(). Именно они и нужны будут нам в дальнейшем для успешного решения задания 8 ЕГЭ по информатике, где требуется находить количество возможных вариантов, удовлетворяющих определённым условиям — будь то количество кодовых слов, комбинаций символов или числовых последовательностей.
Функция product()
Представьте, что вы составляете фруктовое меню из трёх видов фруктов: яблок, бананов и вишни. На каждую позицию вашего меню можно поставить любой из доступных фруктов, причем некоторые фрукты могут повторяться. Как сгенерировать все возможные варианты такого меню?
Или другой пример: вам нужно подсчитать сколько вариантов четырёхзначного PIN-кода существует, при условии, что использоваться могут только цифры.
Подобные задачи относятся к классу задач на размещение с повторением. Решать их вручную можно, но придётся вспомнить формулы комбинаторики и постараться не допустить ошибки в расчётах. И здесь на помощь приходят ваши навыки программирования на Python и функция product() из модуля itertools.
Давайте вспомним, что в математике называется декартовым произведением. По определению, декартово произведение двух множеств A и B — это множество всех упорядоченных пар (a, b), где a принадлежит A, а b принадлежит B. Например, декартово произведение множеств {1, 2} и {X, Y} даст нам пары: (1, X), (1, Y), (2, X), (2, Y).
Переведём рассуждения в более понятную плоскость. Пусть у нас есть два вида супов: борщ и солянка. И два вида вторых блюд: пюре с котлетой и рис с овощами. Как вы уже могли догадаться, у нас есть два множества: супы и вторые блюда. И декартово произведение поможет нам получить все комбинации этих блюд:
- Борщ и пюре
- Борщ и рис
- Солянка и пюре
- Солянка и рис
Звучит вполне очевидно, никаких повторений блюд внутри одного набора у нас нет.
Теперь перейдём ко второму термину — размещению с повторением. Размещение с повторением — это частный случай декартова произведения, когда мы берём произведение множества с самим собой несколько раз.
Например, если у нас есть множество {А, Б} и мы хотим получить все последовательности длины 3, то результатом будут комбинации: (А, А, А), (А, А, Б), (А, Б, А), (А, Б, Б), (Б, А, А), (Б, А, Б), (Б, Б, А), (Б, Б, Б).
Этот пример можем проиллюстрировать следующим образом: представим, что к нам пришло 3 гостя, а у нас в меню есть только 2 супа — борщ и солянка. Таким образом, наша троица может сделать всего 8 вариантов заказов:
Итак, все эти размещения с повторением и декартово произведение мы получили вручную. Но в Python есть функция product(), которая автоматизирует этот процесс и позволяет получать декартово произведение или размещения с повторением.
Она имеет следующий синтаксис:
Параметры функции:
- *iterables — один или несколько итерируемых объектов (списки, строки, кортежи), из которых формируются комбинации.
- repeat — необязательный параметр, определяющий, сколько раз нужно взять декартово произведение множества с самим собой. По умолчанию равен 1.
Именно параметр repeat позволяет переключаться между режимами работы функции. Если repeat=1 (по умолчанию), функция вычисляет обычное декартово произведение переданных множеств. Если repeat больше единицы, генерируются размещения с повторением указанной длины.
Что же, давайте применим эту функцию к рассмотренным выше примерам. Для начала получим декартово произведение наших блюд. Для этого параметр repeat вообще не указываем и передаём в функцию только 2 списка: один с супами, второй — с вторыми блюдами.
Теперь получим размещение с повторениями. Поскольку мы размещаем по 3 элемента, в параметр repeat также передаём число 3. В итоге имеем такой код:
Обратите внимание, что функция product() возвращает итератор! Чтобы вывести сами значения (размещения) нужно получить значения из итератора. Это можно сделать с помощью функции list(), как у нас в примере, либо перебрать все значения в цикле for:
Ну а также можно просто распаковать значения итератора через оператор «*»:
В заключении этой главы рассмотрим пример, типичный для задания 8 ЕГЭ. Требуется найти количество кодовых слов длины 4, составленных из букв {A, B, C}, где буквы могут повторяться:
В результате работы программы, получаем число 81, что означает количество размещений из 3 элементов по 4 или же 3 в степени 4.
Более подробно про количество размещений с повторением и про остальные понятия комбинаторики вы можете прочитать в прошлой статье.
Функция permutations()
Теперь представим другую ситуацию: нужно расставить три книги на полке всеми возможными способами, или составить кодовое слово из букв, где каждая буква используется ровно один раз. Такие задачи относятся к перестановкам — упорядоченным расположениям элементов без повторений.
В задании 8 ЕГЭ часто встречаются формулировки вида «все цифры числа различны» или «каждая буква используется не более одного раза». Для решения подобных задач идеально подходит функция permutations().
Вспомним, что в комбинаторике называется перестановкой элементов. Перестановка — это упорядоченное расположение всех элементов множества. Количество перестановок n элементов равно n! (n факториал). Например, для множества {1, 2, 3} существует 3! = 6 перестановок.
Проиллюстрируем этот пример. Допустим, у нас есть 3 абстрактные книги: зелёная, коричневая и красная. Нам их нужно поставить на полку. Давайте посмотрим, сколько вариантов расстановки трёх книг у нас есть:
- Зелёная, коричневая, красная
- Зелёная, красная, коричневая
- Коричневая, зелёная, красная
- Коричневая, красная, зелёная
- Красная, зелёная, коричневая
- Красная, коричневая, зелёная
Но что, если наша полка вмешает только часть книг, например, две? В таком случае это уже будет размещение без повторений.
Размещение без повторений — это выбор и упорядочение k элементов из n-элементного множества, где каждый элемент может быть выбран только один раз.
Давайте разместим на полке по две книги из нашего набора:
- Зелёная с коричневой
- Зелёная с красной
- Коричневая с зелёной
- Коричневая с красной
- Красная с зелёной
- Красная с коричневой
Функция permutations() умеет генерировать оба варианта в зависимости от переданных параметров. Этим она похожа на уже рассмотренную функцию product(). Только синтаксис параметров немного отличается:
Параметры функции:
- iterable — итерируемый объект (список, строка, кортеж), из которого формируются перестановки.
- r — необязательный параметр, указывающий длину перестановок. Если не указан, используется длина исходного объекта (генерируются перестановки).
Параметр r как раз и позволяет ограничивать длину генерируемых последовательностей, получая таким образом размещения без повторений. Само собой, значение r не может быть меньше количества элементов итерируемого объекта.
Тогда таким кодом можем получить все перестановки наших книг:
А таким — все размещения без повторений из трёх элементов по два:
Заключение
В данной статье мы подробно изучили две ключевые функции модуля itertools, необходимые для решения комбинаторных задач.
Функция product() позволяет генерировать размещения с повторением — комбинации, в которых элементы могут использоваться многократно. Мы научились использовать параметр repeat для указания длины генерируемых последовательностей и увидели, как легко подсчитать количество возможных кодовых слов, когда символы могут повторяться.
Функция permutations() решает противоположную задачу — генерирует перестановки и размещения без повторений, где каждый элемент встречается не более одного раза. Параметр r позволяет ограничивать длину последовательностей, что особенно полезно при работе с задачами, где требуется выбрать лишь часть элементов из исходного множества.
Мы также разобрали теоретические основы: что такое декартово произведение, размещения и перестановки. Понимание этих концепций позволит вам правильно выбирать нужную функцию в зависимости от условия задачи.
Теперь вы владеете всеми нужными инструментами для получения комбинаций и перестановок элементов. В следующей статье мы перейдём от теории к практике и рассмотрим применение функций product() и permutations() к реальным заданиям 8 ЕГЭ по информатике, разобрав типовые формулировки и алгоритм их решения.