1. Комбинаторика на Python: полное руководство по заданию №8 ЕГЭ с разбором задач и кодом
Комбинаторика на Python: полное руководство по заданию №8 ЕГЭ с разбором задач и кодом
Представь, что перед тобой задача: «Из букв слова КОМБАЙН составляются различные шестибуквенные последовательности. Сколько среди них таких, которые начинаются с гласной и заканчиваются на согласную?» Перебирать вручную все варианты — безумие, на это уйдут часы, и легко ошибиться. Но есть способ получить точный ответ за секунды, написав всего несколько строк кода. Именно этот навык — программный перебор и фильтрация комбинаторных объектов — является ключом к быстрому и безошибочному решению задания №8 ЕГЭ по информатике. В этом руководстве мы разберем, как превратить головоломку на перестановки в работающий скрипт на Python.
Три кита комбинаторики: перестановки, размещения, сочетания
Прежде чем писать код, нужно понимать, какой именно комбинаторный объект мы перебираем. От этого зависит, какую функцию из библиотеки itertools мы будем использовать. Представь, что у тебя есть набор уникальных предметов — например, три цветные карандаша: красный, синий, зеленый.
Перестановки — это все возможные порядки, в которые можно разложить все предметы из набора. Для трех карандашей это: (красный, синий, зеленый), (красный, зеленый, синий), (синий, красный, зеленый) и так далее. Важно: используются все* элементы, меняется только порядок. Формула количества перестановок из элементов — это (факториал). Размещения — это выбор и упорядочивание некоторого* количества () предметов из общего набора (). Например, выбрать и расставить на 2 места из наших 3 карандашей: (красный, синий), (красный, зеленый), (синий, красный) и т.д. Здесь важен и выбор, и порядок. Количество размещений: . Сочетания — это просто выбор некоторого количества () предметов из набора (), без учета порядка*. Выбрать 2 карандаша из 3: {красный, синий}, {красный, зеленый}, {синий, зеленый}. Порядок внутри пары не важен. Количество сочетаний: .
> Почему это важно для кода? Ошибка в определении типа задачи — самая частая причина неверного ответа. Если задача про «составить слова» из всех данных букв — это перестановки. Если про «выбрать и расставить» несколько объектов — размещения. Если про «создать комитет» или «выбрать предметы» — это сочетания.
Автоматизация с itertools: от формул к коду
Библиотека itertools — это встроенный в Python набор инструментов для эффективного перебора. Она избавляет нас от написания вложенных циклов вручную.
Перестановки: itertools.permutations
Функция permutations(iterable, r=None) возвращает все возможные перестановки. Если указан параметр r, то генерируются перестановки длиной r (по сути, размещения). Если r не указан — используются все элементы.
Разберем задачу: «Сколько различных трехзначных чисел, больших 300, можно составить из цифр 1, 3, 5, 7, если цифры не повторяются?»
Разбор кода по строкам:
from itertools import permutations — импортируем нужную функцию.digits = ['1', '3', '5', '7'] — задаем исходные элементы. Для permutations это может быть список, строка, кортеж.for p in permutations(digits, 3): — цикл перебирает все возможные кортежи вида ('1', '3', '5'), ('1', '3', '7')... Всего будет варианта.''.join(p) — метод join объединяет элементы кортежа p в строку без разделителей.int(number_str) — преобразуем строку в число для сравнения.if number_int > 300: — это и есть фильтрация по условию задачи. Мы оставляем только те перебранные варианты, которые удовлетворяют условию.Сочетания: itertools.combinations
Функция combinations(iterable, r) возвращает все возможные сочетания по r элементов. Порядок в результатах всегда лексикографический, что исключает дубли.
Задача: «В магазине 5 разных фруктов. Сколькими способами можно выбрать 3 фрукта для салата?»
Здесь фильтрация не нужна — мы сразу получаем точное количество. Но если бы условие было, например, «...при условии, что в салате обязательно есть яблоко», пришлось бы добавить проверку:
Размещения: itertools.permutations с параметром r
Как уже упоминалось, для генерации размещений мы используем ту же функцию permutations, но с явным указанием длины r. Именно так мы делали в примере с трехзначными числами.
Сложная фильтрация: когда условие — это комбинация проверок
Большинство задач №8 требуют не просто пересчета, а отбора вариантов по нескольким критериям. Рассмотрим задачу-классику: «Из букв слова ПАРУС составляются все возможные пятибуквенные последовательности. Сколько среди них таких, которые начинаются с гласной и не содержат двух подряд идущих гласных?»
Здесь два условия: 1) первая буква — гласная; 2) в последовательности нет двух гласных подряд. Буквы в слове ПАРУС могут повторяться? Нет, в условии «из букв слова» обычно подразумевается использование данных букв без повторений, если не сказано иное. Значит, это перестановки всех 5 букв.
Ключевые моменты логики фильтрации:
continue: Если первое условие не выполнено, мы сразу переходим к следующей итерации цикла, не тратя время на проверку второго условия. Это оптимизация.len(p)-2 и сравниваем соседние элементы. Флаг has_double_vowel устанавливается в True при первом же нарушении.vowels = {'А', 'У'} — это множество (set). Проверка in для множества происходит мгновенно, в отличие от списка.Интерпретация результата и типичные ловушки
Получить число — это полдела. Нужно убедиться, что мы посчитали именно то, что просили.
Ловушка 1: Повторяющиеся элементы. Если в исходном наборе есть одинаковые элементы (например, слово «КОМБАЙН» содержит две гласные, но они разные — О и А), то permutations будет генерировать дубли? Нет, функция рассматривает позиции элементов как уникальные, даже если значения совпадают. Но если бы в слове были две буквы «А» (как в слове «МАССА»), то permutations сгенерировал бы одинаковые перестановки, где эти две «А» меняются местами. В этом случае нужно использовать set(permutations(word)) для удаления дублей перед фильтрацией.
Ловушка 2: Длина последовательности. Внимательно читаем: составляются ли все последовательности из всех букв (перестановки) или последовательности заданной длины (размещения)? От этого зависит, передаем ли мы параметр r в функцию.
Ловушка 3: Смысл фильтра. Условие «содержит подстроку "АУ"» означает, что две конкретные буквы должны стоять подряд и именно в таком порядке. Это проверяется так:
Общий алгоритм решения задания №8
Подведем итог. Любой скрипт для задания №8 строится по одному шаблону:
itertools:permutations(iterable) — для перестановок всех элементов.
* permutations(iterable, k) — для размещений (выбор и порядок элементов).
* combinations(iterable, k) — для сочетаний (выбор элементов без порядка).
for item in function(...)).if, continue, проверки in, сравнения строк/чисел, проверки соседних элементов.count += 1) только для тех вариантов, которые прошли все проверки.Этот подход превращает сложную комбинаторную головоломку в задачу на написание четкого, пошагового алгоритма. Вместо того чтобы пытаться высчитать все в уме и упустить какой-нибудь случай, ты доверяешь перебор компьютеру, а сам сосредотачиваешься на правильной формулировке условий фильтрации. Практикуйся на разборе конкретных вариантов, и很快 (очень скоро) ты будешь решать задание №8 не только верно, но и с завидной скоростью.