Что проверяет задание

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

Определения

Алфавит, упорядоченный набор символов. Порядок букв алфавита задаёт порядок слов.

Слово, конечная последовательность символов алфавита. Длина слова, число позиций.

Размещение с повторениями, слово, в котором символы независимы: на каждую позицию можно поставить любой символ алфавита, если условие не запрещает.

Размещение без повторений, слово, в котором все символы различны.

Перестановка, размещение без повторений, в котором использованы все символы набора.

Сочетание, набор символов без учёта порядка.

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

Правило суммы, если варианты разбиты на непересекающиеся случаи, их количества складывают.

Дополнение, иногда проще посчитать все слова данной длины и вычесть запрещённые.

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

Номер слова, его позиция в полном списке всех допустимых слов, выписанных в лексикографическом порядке. Нужно внимательно смотреть, нумерация с нуля или с единицы.

Типичные ограничения

• фиксированная длина;
• запрет одинаковых соседних символов;
• запрет определённых букв рядом;
• слово должно содержать данный символ хотя бы раз;
• первая цифра числа не может быть нулём;
• слово читается как число в системе счисления.

Ограничение «не стоят рядом» затрагивает пары позиций, поэтому шаги выбора уже не полностью независимы: удобно идти по позициям слева направо и помнить предыдущий символ.

Общий алгоритм решения

1. Зафиксировать алфавит, его порядок и длину слова.
2. Перевести словесные запреты на язык свойств позиций и символов.
3. Если нужен подсчёт, выбрать: прямое правило произведения, разбиение на случаи или дополнение.
4. Если нужен номер слова, определить, сколько слов идёт строго раньше данного: для каждой позиции посчитать, сколько меньших букв можно было поставить, умножить на число продолжений.
5. Для чисел отдельно обработать ведущий нуль: это не цифра в обычном смысле записи числа.
6. Записать ответ как целое количество или как номер, в точности в той нумерации, которую задало условие.

Программа построчно

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

Разберём программу на условии:

Составляются 5-буквенные слова из букв К, Л, М, Н, П. Буквы могут повторяться. Сколько слов, у которых на втором месте не может стоять буква Н?

from itertools import product

count = 0
for w in product("КЛМНП", repeat=5):
    if w[1] != "Н":
        count += 1
print(count)

from itertools import product - подключаем функцию product из стандартного модуля itertools («инструменты для перебора»). Она умеет выдавать все слова заданной длины из заданного алфавита.

count = 0 - счётчик подходящих слов. Перед перебором он равен нулю.

for w in product("КЛМНП", repeat=5): - главный цикл. product по очереди выдаёт все слова длины 5 из букв К, Л, М, Н, П: «ККККК», «ККККЛ», «ККККМ», …, «ППППП». Каждое слово попадает в переменную w. Подробно - в разделе «Перебор: product».

if w[1] != "Н": - условие из задачи. w[1] - вторая буква слова (нумерация в Python с нуля: w[0] - первая буква, w[1] - вторая). Знак != означает «не равно».

count += 1 - если слово подходит, увеличиваем счётчик на единицу.

print(count) - после перебора печатаем, сколько набралось. Ответ: 2500 (всего 5⁵ = 3125 слов, из них у 625 на втором месте Н).

Перебор: product

product(алфавит, repeat=n) выдаёт все последовательности длины n, где на каждом месте может стоять любой символ алфавита - с повторениями.

from itertools import product

for w in product("АБ", repeat=3):
    print(w)

Программа напечатает 8 строк:

('А', 'А', 'А')
('А', 'А', 'Б')
('А', 'Б', 'А')
('А', 'Б', 'Б')
('Б', 'А', 'А')
...
('Б', 'Б', 'Б')

Что важно знать:

• w - не строка, а кортеж символов: ('А', 'Б', 'А'). К его элементам обращаются по номеру (w[0]), у него есть метод count, но склеить в строку его нужно отдельно (см. «Строка из кортежа»).
• Слов всегда k^n, где k - число символов алфавита, n - длина. Для 5 букв и длины 5 это 3125 - перебор займёт мгновение.
• Порядок выдачи - «как в словаре», но по порядку символов в строке-алфавите: сначала все слова на первую букву строки, потом на вторую и так далее. Поэтому для заданий «по алфавиту» буквы в строке нужно записать по алфавиту.
• Алфавит - это различные буквы. Если слово в условии «ВЕТЕР», в алфавит идут В, Е, Т, Р: вторая буква Е новых слов не добавляет. Запись product("ВЕТЕР", …) посчитает одни и те же слова дважды - это ошибка.

Счётчик

count = 0
for w in product(...):
    if условие:
        count += 1
print(count)

count += 1 - сокращённая запись count = count + 1. Строка выполняется только для подходящих слов, поэтому после цикла в count лежит их количество. Печатаем его после цикла - без отступа, иначе число напечатается для каждого слова.

Если условий несколько, их соединяют словом and («и»): слово подходит, только если выполнены все условия.

Условие на количество

Сколько раз символ встречается в слове, считает метод count (у кортежа он такой же, как у строки):

• «буква А встречается ровно 2 раза» → w.count("А") == 2;
• «не менее 2 раз» (2 или больше) → w.count("А") >= 2;
• «не более 3 раз» → w.count("А") <= 3;
• «хотя бы один раз» → w.count("А") >= 1;
• «не содержит букву А» → "А" not in w.

Пример: для слова ('К', 'А', 'Р', 'А', 'Т') значение w.count("А") равно 2.

Условие на позицию

Позиции в Python считаются с нуля:

• первая буква - w[0], вторая - w[1], k-я - w[k - 1];
• последняя - w[-1] (отрицательный номер считается с конца).

Примеры:

• «слово начинается с буквы А» → w[0] == "А";
• «не начинается с А» → w[0] != "А";
• «не заканчивается на А» → w[-1] != "А";
• «на втором месте не может стоять Н» → w[1] != "Н";
• «первая буква - гласная» → w[0] in vowels.

Соседние символы

Условия вида «две гласные не стоят рядом» проверяют каждую пару соседей. В слове длины 5 пар четыре: (w[0], w[1]), (w[1], w[2]), (w[2], w[3]), (w[3], w[4]). Номер первой буквы пары i пробегает range(4) - то есть 0, 1, 2, 3.

all(not (w[i] in vowels and w[i + 1] in vowels) for i in range(4))

Читается так: «для всех i от 0 до 3 неверно, что и w[i], и w[i + 1] - гласные». Подробно про all - в разделе «all и any».

Другие формулировки:

• «никакие две согласные не стоят рядом» → not (w[i] not in vowels and w[i + 1] not in vowels) - согласная - это буква не из гласных;
• «чётные и нечётные цифры чередуются» («никакие две чётные и никакие две нечётные не стоят рядом») → int(w[i]) % 2 != int(w[i + 1]) % 2 - у соседей разный остаток от деления на 2;
• «цифры следуют в невозрастающем порядке» → w[i] >= w[i + 1] - каждая цифра не меньше следующей (символы-цифры сравниваются так же, как числа);
• «буквы А и Б не стоят рядом (в любом порядке)» → удобнее через строку: "АБ" not in s and "БА" not in s, где s = ''.join(w);
• «нечётная цифра не стоит рядом с 4» → выписываем все запрещённые пары и проверяем, что ни одной нет в строке: all(pair not in s for pair in ("41", "14", "43", "34", …)).

Все символы различны

len(set(w)) == len(w)

set(w) - множество символов слова: повторы в нём хранятся один раз. Для ('Т', 'О', 'Р', 'Т') множество - {'Т', 'О', 'Р'}, в нём 3 элемента, а в слове 4 символа - значит, был повтор. Если длины совпали, все символы различны.

Так же записывают «каждая буква входит в код ровно один раз».

Числа в системе счисления

n-значное число в системе с основанием b - это последовательность из n цифр от 0 до b − 1, у которой первая цифра не ноль (иначе число окажется короче).

from itertools import product

count = 0
for w in product("01234567", repeat=5):
    if w[0] != "0" and w.count("7") == 1:
        count += 1
print(count)

• "01234567" - цифры восьмеричной системы. Для десятичной - "0123456789", для шестнадцатеричной - "0123456789ABCDEF" (A = 10, …, F = 15).
• w[0] != "0" - число именно пятизначное.
• Цифры в w - символы. Чтобы считать с ними (чётность, сравнение «больше»), их переводят в числа: int(w[i]). Для систем с основанием больше 10 нужно указать основание: int("A", 12) = 10.
• «Число делится на 5» → склеиваем запись в строку и переводим в число с учётом основания: int(s, 8) % 5 == 0.

Сумма по цифрам

Когда условие про сумму или количество цифр с каким-то свойством, удобна запись sum(… for d in w):

• sum(int(d) for d in w) - сумма всех цифр;
• sum(int(d, 12) > 8 for d in w) - сколько цифр больше 8: сравнение > даёт True (1) или False (0), а sum складывает эти единицы;
• sum(int(d) for d in w[1:-1]) - сумма всех цифр, кроме первой и последней: срез w[1:-1] отбрасывает крайние.

Строка из кортежа

s = ''.join(w)

''.join(...) склеивает символы кортежа в одну строку без разделителей: ('В', 'Е', 'Т') → 'ВЕТ'. Строка нужна, когда в слове ищут кусок из нескольких букв ("АБ" in s) или когда запись переводят в число (int(s, 8)).

Гласные и согласные

vowels = "АЕЁИОУЫЭЮЯ"

Строка со всеми гласными русского алфавита. Проверка буква in vowels отвечает, гласная ли буква: "Е" in vowels → True, "Т" in vowels → False. Согласная - всё, что не входит в эту строку: буква not in vowels. Если в условии отдельно перечислены гласные («гласные: А, Е, И, О, У»), используют именно их.

all и any

• all(условие for i in range(4)) - True, только если условие верно для каждого i;
• any(условие for i in range(4)) - True, если условие верно хотя бы для одного i.

Запись внутри скобок - генератор: «для каждого i из range(4) проверить условие». Это короткая замена циклу:

ok = True
for i in range(4):
    if w[i] in vowels and w[i + 1] in vowels:
        ok = False

После цикла ok равно тому же, что all(not (w[i] in vowels and w[i + 1] in vowels) for i in range(4)).

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

Если все слова выписаны в алфавитном порядке и пронумерованы с 1, список удобно построить программой:

from itertools import product

words = [''.join(w) for w in product("АГЛОЬ", repeat=5)]
print(words.index("ОЛЬГА") + 1)

• Буквы в строке записаны по алфавиту (А, Г, Л, О, Ь) - тогда product выдаёт слова ровно в том порядке, что и в условии.
• [''.join(w) for w in product(...)] - список всех слов-строк по порядку.
• words.index("ОЛЬГА") - позиция слова в списке, считая с нуля. Номера в условии начинаются с 1, поэтому прибавляем 1.
• Слово по номеру: words[69 - 1] - номер 69 в условии - это индекс 68 в Python.
• Если каждая буква входит в код ровно один раз, в список берут только слова без повторов: if len(set(w)) == длина.

Первое слово с условием

for i, w in enumerate(words):
    if w[0] == "Н":
        print(i + 1)
        break

• enumerate(words) выдаёт пары (номер, слово): (0, 'ВВВВ'), (1, 'ВВВК'), … Номер считается с нуля, поэтому печатаем i + 1.
• break останавливает цикл: нужно первое подходящее слово.

Для последнего подходящего слова цикл проходит до конца и запоминает номер каждого подходящего:

last = 0
for i, w in enumerate(words):
    if w.count("Е") == 1:
        last = i + 1
print(last)

После цикла в last останется номер последнего подходящего слова.

Номер кода: позиционная запись

«Составляется список всех кодов из латинских букв: сначала коды из одного символа (A, …, Z), затем из двух (AA, AB, …, ZZ), затем из трёх и так далее. Под каким номером окажется код JCSDMT?»

Перебрать все коды программой можно, но кодов длины до 6 больше 300 миллионов - это очень долго. Номер считают по формуле.

alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
code = "JCSDMT"

number = 0
for length in range(1, len(code)):
    number += 26 ** length

pos = 0
for ch in code:
    pos = pos * 26 + alphabet.index(ch)

print(number + pos + 1)

Сначала идут все более короткие коды. Кодов длины L ровно 26^L: на каждое из L мест - любая из 26 букв. Цикл складывает 26 + 26² + … + 26⁵ - столько кодов стоит перед всеми шестибуквенными.

Потом - коды той же длины, стоящие раньше нашего. Коды одной длины идут по алфавиту так же, как числа в системе счисления с основанием 26, если считать A = 0, B = 1, …, Z = 25. Например, для двухбуквенных: AA = 0, AB = 1, …, AZ = 25, BA = 26.

• alphabet.index(ch) - «цифра» буквы: её номер в алфавите с нуля;
• pos = pos * 26 + … - та же схема, что при переводе записи числа в десятичную систему (схема Горнера): к накопленному значению приписываем следующую цифру;
• после цикла pos - сколько кодов той же длины стоит перед нашим.

Номер = более короткие коды + коды той же длины перед нашим + 1 (сам код).