156 subscribers

ITERTOOLS комбинаторика на Python решаем 8-е задание без труда

786 full reads

Большинство заданий №8 из КЕГЭ по информатике связано с комбинаторикой - перестановками, сочетаниями, количеством вариантов выборки и т.д. Модуль ITERTOOLS предназначен для таких задач (ссылка на документацию - https://docs.python.org/3/library/itertools.html ). Разберём его основные функции

PRODUCT - сочетания с повторениями

print(product(*'AB', repeat=3))

(‘A’, ‘A’, ‘A’) (‘A’, ‘A’, ‘B’) (‘A’, ‘B’, ‘A’) (‘A’, ‘B’, ‘B’) (‘B’, ‘A’, ‘A’) (‘B’, ‘A’, ‘B’) (‘B’, ‘B’, ‘A’) (‘B’, ‘B’, ‘B’)

Функция принимает на вход строку символов и длину комбинаций. В примере мы получили все возможные комбинации длиной 3 из двух букв АВ.

Пример задачи

Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Игорь использует 5-буквенные слова, в которых есть только буквы П, И, Р, причём буква П появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Игорь?

Решение

ITERTOOLS комбинаторика на Python решаем 8-е задание без труда

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

PERMUTATIONS - перестановки

print(*permutations(‘ABC’))

(‘A’, ‘B’, ‘C’) (‘A’, ‘C’, ‘B’) (‘B’, ‘A’, ‘C’) (‘B’, ‘C’, ‘A’) (‘C’, ‘A’, ‘B’) (‘C’, ‘B’, ‘A’)

Мы получили все комбинации путём перестановки букв A, B и C.

Пример задачи

Петя составляет семибуквенные слова перестановкой букв слова ТРАТАТА. Сколько всего различных слов может составить Петя?

ITERTOOLS комбинаторика на Python решаем 8-е задание без труда

Обратите внимание на четвёртую строку: из-за того, что в слове "ТРАТАТА" повторяются буквы Т и А, получилось очень много дублей. Для того, чтобы их удалить, применили функцию SET. Она превратила список в множество, тем самым убрав повторы значений.

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

Удачи!