Перебор слов в Python: product, permutations и задание 8 ЕГЭ

Сначала определяем, какие слова разрешены

В задачах на перебор «словом» называют последовательность символов, а не обязательно слово из словаря. Из букв А, Б, В можно составить ААБ, ВБА и другие последовательности. Важны три условия: алфавит, длина и допустимость повторений.

Если длина равна 3 и каждую из трёх букв можно брать сколько угодно раз, получаем 3 × 3 × 3 = 27 слов. Если нужны только последовательности без повторений — 3 × 2 × 1 = 6. Порядок важен: АБВ и ВБА — разные слова.

Здесь собственные учебные примеры по теме задания 8 ЕГЭ. Сначала посчитайте маленький пример вручную, затем используйте программу для проверки.

product: слова с повторениями и двумя ограничениями

Условие. Составляем четырёхбуквенные слова из А, Б, В. Буквы могут повторяться. Буква А должна встретиться ровно один раз, а слово не должно начинаться с Б.

Функция product("АБВ", repeat=4) перебирает все 3⁴ = 81 последовательность. Она возвращает кортежи символов; "".join(letters) собирает строку. Проверяем оба ограничения через and:

from itertools import product

count = 0
for letters in product("АБВ", repeat=4):
    word = "".join(letters)
    if word.count("А") == 1 and word[0] != "Б":
        count += 1
print(count)  # 20

Проверка без кода. Если А стоит первой, в трёх остальных позициях по два варианта: 2³ = 8. Если А стоит в одной из трёх других позиций, первой должна быть В, а в двух свободных позициях остаются Б или В: 3 × 2² = 12. Всего 8 + 12 = 20.

word.count("А") == 1 означает «ровно одна А». Условие "А" in word означает «хотя бы одна» и даст другой ответ. В строке алфавита используются кириллические буквы; латинская A — другой символ.

Соседние буквы: что именно запрещено

Для запрета двух А подряд достаточно "АА" not in word. Для запрета любых одинаковых соседей нужно сравнить все соседние пары:

allowed = all(word[i] != word[i + 1] for i in range(len(word) - 1))

У четырёхбуквенного слова из А, Б, В без одинаковых соседей 3 варианта первой буквы и по 2 варианта каждой следующей. Получается 3 × 2³ = 24. Несоседние буквы повторяться могут: АБАВ подходит.

permutations: без повторений и с одинаковыми буквами

Если выбираем три разные буквы из А, Б, В, Г и учитываем их порядок, используем permutations("АБВГ", 3). Получится 4 × 3 × 2 = 24.

Но одинаковые символы во входной строке — отдельная ловушка. В слове ТОПОТ две Т и две О. permutations различает позиции исходных букв, поэтому одинаковые строки появляются несколько раз.

from itertools import permutations

print(sum(1 for _ in permutations("АБВГ", 3)))  # 24
unique_words = {"".join(p) for p in permutations("ТОПОТ")}
print(len(unique_words))  # 30

Для ТОПОТ число различных перестановок равно 5! ÷ (2! × 2!) = 30. Множество set убирает повторы строк; для этого маленького примера оно удобно. На больших входах число перестановок растёт очень быстро — не сохраняйте огромный перебор в память.

combinations здесь не заменяет permutations: комбинации не перебирают все порядки выбранных букв. В этих заданиях порядок символов важен.

Номер слова в алфавитном списке

Пусть все трёхбуквенные слова из А, Б, В записаны в порядке А < Б < В, нумерация начинается с 1. Нужно найти номер слова БАВ. Передайте буквы в product именно в требуемом порядке:

from itertools import product

for number, letters in enumerate(product("АБВ", repeat=3), start=1):
    word = "".join(letters)
    if word == "БАВ":
        print(number)  # 12
        break

Независимая проверка: заменим А, Б, В цифрами 0, 1, 2. БАВ соответствует 102₃: 1 × 9 + 0 × 3 + 2 = 11. Это номер с нуля, поэтому прибавляем 1: ответ 12.

Где ставить счётчик? Если нужен номер в полном списке, нумеруйте до фильтрации. Если нужно количество подходящих слов, увеличивайте count только после проверки условий. Если условие нумерует уже отобранный список, это нужно реализовать отдельно.

Когда вместо слов трёхзначные числа

Составим чётные трёхзначные числа из цифр 0–5 без повторения цифр. Начальная цифра не может быть нулём; последняя должна быть 0, 2 или 4.

from itertools import product

count = 0
for digits in product("012345", repeat=3):
    word = "".join(digits)
    if word[0] != "0" and len(set(word)) == 3 and int(word[-1]) % 2 == 0:
        count += 1
print(count)  # 52

Проверяем ответ по случаям. При последней цифре 0 есть 5 вариантов первой и 4 второй: 20. При последней цифре 2 или 4 — по 4 варианта первой (без нуля и выбранной последней) и 4 второй: 2 × 4 × 4 = 32. Всего 52.

Для цифрового кода начальный ноль может быть разрешён. Для трёхзначного числа — нет. Ограничение зависит от формулировки задачи.

Файл с примерами и следующий шаг

Скачать все четыре программы Python. Если файл сохранится с расширением .py.txt, уберите последнее .txt. Последовательный запуск примеров выведет: 20, 24, 30, 12, 52 — каждое число на отдельной строке.

1. Уточните алфавит, длину и повторения.
2. Выберите product или permutations.
3. Запишите каждое ограничение отдельно и соедините проверки.
4. Отделите подсчёт количества от нумерации полного списка.
5. Проверьте результат на маленьком примере вручную.

О поведении функций — в документации itertools. Далее — шесть задач ниже и подборка задания 8 ЕГЭ.

Первое слово с чётным номером: пример КЕГЭ №31505

В КЕГЭ №31505, демоверсия 2027 рассматривается список пятибуквенных слов из А, К, Ц, Е, Н, Т. Нужно найти первое слово с чётным номером, которое начинается не с А, Е или К и содержит хотя бы одну Т. Повторения букв разрешены; нумерация полного списка начинается с 1.

Сначала расставьте алфавит: А Е К Н Т Ц. Счётчик увеличивается для каждого слова, до проверки условий. break останавливает поиск сразу после первого подходящего.

from itertools import product

n = 0
for word in product('АЕКНТЦ', repeat=5):
    n += 1
    if n % 2 == 0 and word[0] not in 'АЕК' and 'Т' in word:
        print(n)
        break

Ответ: 3914, слово НААТЕ. Проверка вручную: заменяем буквы цифрами 0…5. НААТЕ → 30041₆; номер равен 3 × 6⁴ + 4 × 6 + 1 + 1 = 3914. Слова НАААТ и НААЕТ содержат Т, но стоят под нечётными номерами; НААКТ тоже. НААТА имеет номер 3913, следующий вариант НААТЕ уже подходит.

Если ищут последнее слово, уберите break и сохраняйте номер каждого подходящего варианта; вывод делайте после цикла. Если ищут количество слов, заведите отдельный счётчик подходящих — это другая величина.

От учебного примера к экзаменационному условию

Когда маленький перебор уже понятен, попробуйте задание ЕГЭ №12240 с условием и разбором. Сначала выпишите алфавит, длину слова и ограничения. Для проверки короткой программы используйте Python онлайн.

Проверьте себя

Сначала решите самостоятельно. Затем проверьте ответ или откройте объяснение.