Модуль itertools: функции product и permutations

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

В Python для этого есть встроенный модуль itertools. Он содержит функции для работы с итераторами и позволяет решать многие комбинаторные задачи в несколько строк кода.

Подробно изучать итераторы мы не будем. В этой статье сосредоточимся на двух полезных функциях: product() и permutations(). Они понадобятся нам для решения задания 8 ЕГЭ по информатике.

Функция product()

Представьте, что три гостя выбирают один из двух супов: борщ или солянку. Выбор каждого гостя не зависит от остальных, поэтому блюда могут повторяться. Как получить все возможные варианты заказов?

Другой пример: нужно подсчитать, сколько существует четырёхзначных PIN-кодов, если можно использовать только заданные цифры и цифры могут повторяться.

Такие задачи относятся к размещениям с повторениями. Их можно решать по формулам, но функция product() из модуля itertools позволяет сразу сгенерировать все варианты и проверить дополнительные условия.

Сначала вспомним декартово произведение. Декартово произведение множеств A и B — это множество всех упорядоченных пар (a, b), где a принадлежит A, а b — множеству B. Например, для {1, 2} и {X, Y} получим (1, X), (1, Y), (2, X), (2, Y).

Рассмотрим более наглядный пример. Пусть есть два супа — борщ и солянка — и два вторых блюда: пюре и рис. Декартово произведение этих наборов даст все варианты обеда:

1. Борщ и пюре
2. Борщ и рис
3. Солянка и пюре
4. Солянка и рис

Здесь всё достаточно очевидно: из каждого набора мы выбираем по одному элементу.

Теперь перейдём к размещениям с повторениями. Их можно представить как декартово произведение одного набора с самим собой несколько раз.

Например, если у нас есть множество {А, Б} и мы хотим получить все последовательности длины 3, то результатом будут комбинации:

1. (А, А, А),
2. (А, А, Б),
3. (А, Б, А),
4. (А, Б, Б),
5. (Б, А, А),
6. (Б, А, Б),
7. (Б, Б, А),
8. (Б, Б, Б).

Проиллюстрируем этот пример иначе. К нам пришли три гостя, и каждый выбирает борщ или солянку. Всего получится 2³ = 8 вариантов заказов:

Мы получили декартово произведение и размещения с повторениями вручную. В Python тот же перебор выполняет функция product().

Она имеет следующий синтаксис:

product(*iterables, repeat=1)

Параметры функции:

• *iterables — один или несколько итерируемых объектов: строк, списков или кортежей, из которых формируются комбинации;
• repeat — необязательный параметр, показывающий, сколько раз повторить набор переданных объектов. По умолчанию repeat=1.

Если передать несколько объектов без repeat, product() построит их декартово произведение. Если передать один объект и repeat больше единицы, функция сгенерирует последовательности заданной длины с повторениями.

Применим функцию к рассмотренным примерам. Сначала получим декартово произведение блюд: передадим список супов и список вторых блюд, а repeat указывать не будем.

from itertools import product

soups = ["Борщ", "Солянка"]
meals = ["Пюре", "Рис"]

result = product(soups, meals)

print(list(result))

Теперь получим размещения с повторениями. Нам нужны последовательности из трёх элементов, поэтому укажем repeat=3:

from itertools import product

soups = ["Борщ", "Солянка"]

result = product(soups, repeat=3)

print(list(result))

Обратите внимание: product() возвращает итератор. Чтобы увидеть все значения, его можно преобразовать в список с помощью list() или перебрать в цикле for:

from itertools import product

soups = ["Борщ", "Солянка"]

result = product(soups, repeat=3)

for res in result:
    print(res)

Также значения итератора можно распаковать оператором *:

from itertools import product

soups = ["Борщ", "Солянка"]

result = product(soups, repeat=3)

print(*result)

В завершение раздела рассмотрим пример, близкий к заданию 8. Нужно найти количество четырёхбуквенных слов из букв A, B и C. Буквы могут повторяться:

from itertools import product

letters = 'ABC'

count = len(list(product(letters, repeat=4)))

print(count)

Программа выведет 81. Это количество последовательностей длины 4, составленных из трёх символов: 3 · 3 · 3 · 3 = 81.

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

Функция permutations()

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

В задании 8 встречаются условия «все цифры различны» или «каждая буква используется не более одного раза». Для такого перебора подходит функция permutations().

Перестановка — это упорядоченное расположение всех элементов множества. Количество перестановок n различных элементов равно n!. Например, для множества {1, 2, 3} существует 3! = 6 перестановок.

Проиллюстрируем это на трёх книгах: зелёной, коричневой и красной. Посмотрим, какими способами их можно расставить на полке:

1. Зелёная, коричневая, красная
2. Зелёная, красная, коричневая
3. Коричневая, зелёная, красная
4. Коричневая, красная, зелёная
5. Красная, зелёная, коричневая
6. Красная, коричневая, зелёная

Но что, если на полке помещается только часть книг, например две? Тогда получаются размещения без повторений.

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

Давайте разместим на полке по две книги из нашего набора:

1. Зелёная с коричневой
2. Зелёная с красной
3. Коричневая с зелёной
4. Коричневая с красной
5. Красная с зелёной
6. Красная с коричневой

Функция permutations() умеет генерировать и перестановки, и размещения без повторений. Результат зависит от второго параметра:

permutations(iterable, r=None)

Параметры функции:

• iterable — итерируемый объект: строка, список или кортеж, из которого формируются последовательности;
• r — необязательный параметр, задающий длину последовательности. Если его не указать, используется длина исходного объекта и генерируются полные перестановки.

Параметр r позволяет получать размещения без повторений нужной длины. Его значение не может быть больше количества элементов исходного объекта.

Таким кодом получим все перестановки трёх книг:

from itertools import permutations

books = ["Зелёная", "Коричневая", "Красная"]

result = permutations(books)

print(list(result))

А таким — все размещения без повторений из трёх элементов по два:

from itertools import permutations

books = ["Зелёная", "Коричневая", "Красная"]

result = permutations(books, r=2)

print(list(result))

Итоги

В этой статье мы изучили две функции модуля itertools, полезные для решения комбинаторных задач.

Функция product() генерирует декартовы произведения и размещения с повторениями. Параметр repeat задаёт длину последовательностей, если один и тот же набор используется несколько раз.

Функция permutations() генерирует перестановки и размещения без повторений. Параметр r позволяет задать длину последовательности, когда требуется выбрать только часть элементов.

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

Теперь у нас есть инструменты для перебора комбинаций и перестановок. В следующей статье применим product() и permutations() к типовым заданиям 8 ЕГЭ по информатике.