Задание номер 8 — задание базового уровня сложности, выполнение которого предполагает знание о методах измерения количества информации и не требует использования специального ПО.
Зачастую в номере 8 мы можем встретить задания связанные с комбинаторикой — перестановками, количеством вариантов выборки и т.д. Для решения заданий такого типа можно приспособить модуль itertools языка python.
Сразу оговорюсь, что я не рекомендую решать задание именно таким способом. Я советую проверять свой ответ, полученный ручным решением. Написанная программа не должна быть единственным вариантом решения.
Модуль itertools доступен в питоне «из коробки», т.е. его нет необходимости устанавливать дополнительно. А значит, он будет доступен на экзамене.
Ссылка на документацию по модулю https://docs.python.org/3/library/itertools.html
Использованные в данной статье методы и функции доступны как минимум с версии питона 3.6
Для импорта необходимых функции необходимо их импортировать из модуля
from itertools import product, permutations
- product
Позволяет получить прямое, или декартово произведеение двух множеств — множество, элементами которого являются все возможные упорядоченные пары элементов исходных множеств.
a = ‘AB’
b = ‘CD’
print(*product(a, b))
(‘A’, ‘C’) (‘A’, ‘D’) (‘B’, ‘C’) (‘B’, ‘D’)
Получение произведения двух множеств не очень актуально в 8 задании, но мы можем использовать другую возможность функции product: получение всевозможных комбинаций определенной длины для одного множества.
a = ‘AB’
print(*product(a, 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 для набора из двух букв АВ. Причем результат работы функции — набор кортежей.
Параметр repeat отвечает за длину слова.
Из полученных наборов мы можем выбрать подходящие для нас. Например, так можно решить задание из демоверсии 2021.
Длина слова здесь 3, а набор букв — ШКОЛА. Получим всевозможные комбинации:
a = ‘ШКОЛА’
comb = product(a, repeat=3))
Осталось выбрать те, где буква К встречается ровно 1 раз.
Поскольку подсчет количества вхождений в кортеж организовать сложнее, чем в строке, здесь элементы кортежа «склеиваются» по пустой строке, образуя тем самым не кортеж, а строку. Метод count подсчитывает количество вхождений подстроки ‘K’.
Этот же код можно оформить в одну строку через списочное выражение
print(len([item for item in product(‘ШКОЛА’, repeat=3) if ”.join(item).count(‘К’) == 1]))
2. permutations
Позволяет получить всевозможные перестановки.
print(*permutations(‘ABC’))
(‘A’, ‘B’, ‘C’) (‘A’, ‘C’, ‘B’) (‘B’, ‘A’, ‘C’) (‘B’, ‘C’, ‘A’) (‘C’, ‘A’, ‘B’) (‘C’, ‘B’, ‘A’)
Это опять набор кортежей.
Рассмотрим такое задание с сайта kpolyakov.spb.ru
Получаем перестановки
a = ‘КАПКАН’
comb = permutations(a)
И отбираем нужные варианты
Поскольку в слове КАПКАН есть повторяющиеся буквы А и К, мы должны поделить итоговое количество на 4 (дважды поделить на 2), поскольку с нашей точки зрения эти комбинации неотличимы друг от друга.
Другой способ убрать повторяющиеся комбинации — превратить набор перестановок в множество, которое в питоне исключает повторы
Так-же можно написать решение в одну строку
print(len([i for i in set(permutations(‘КАПКАН’)) if all(i[j] != i[j + 1] for j in range(5))]))
Подведем итог. Задачи на составление слов путем выбора букв из набора или путем перестановки букв в слове можно решить с использованием модуля itertools. Написание кода не займет много времени, зато будет уверенность в ручном решении.