Задание 8: комбинаторика слов и чисел

Задание 8 — про подсчёт слов и чисел, и вопросов в нём всего два.

Сколько слов удовлетворяют условию. Формулировка из банка: «Все слова, состоящие из 6 букв, в которых могут использоваться только буквы А Д К Л О, записаны в некотором порядке. Буквы в слове могут повторяться. Сколько существует таких слов, в которых буква Л встречается ровно 2 раза?» Условие меняется — «ровно одна цифра 3», «не содержит буквы Ь», «нет двух одинаковых подряд», «цифра 0 не стоит рядом с цифрой 3» — но вопрос один: посчитать.

Какой номер у слова или какое слово под номером. «Все пятибуквенные слова из букв М А С Л О записаны в алфавитном порядке и пронумерованы начиная с 1. Под каким номером идёт первое слово, которое…» Здесь работает связь слов с числами в позиционной системе счисления, и о ней вторая половина урока.

Важная общая деталь: буквы могут повторяться. Это сказано в условии прямым текстом и означает, что речь не о перестановках и не о сочетаниях, а о размещениях с повторениями. Слов длины L из алфавита размера m ровно m^L, и никакие факториалы здесь не нужны.

И вторая: слов в линии 8 всегда немного. Пять букв, длина шесть — это 15 625 вариантов; шесть букв, длина шесть — 46 656. Компьютер перебирает их за доли секунды. Поэтому главный инструмент линии 8 — не формула, а перебор, и формулы нужны скорее для проверки.

Почему слов длины L из алфавита размера m ровно m^L?

Строим слово по одной букве. На первую позицию можно поставить любую из m букв. Независимо от того, что там оказалось, на вторую позицию снова годятся все m букв — повторения разрешены. И так далее. Число способов перемножается: m · m · … · m, L раз.

Это правило произведения: если действие состоит из независимых шагов и на каждом шаге есть своё число вариантов, общее число исходов равно произведению.

Отсюда же считаются варианты с ограничениями на отдельные позиции. «Пятизначное число в четверичной системе» — это слово длины 5 из цифр 0, 1, 2, 3, но первая цифра не может быть нулём, иначе число не пятизначное. Значит, вариантов 3 · 4 · 4 · 4 · 4 = 768, а не 4⁵ = 1024.

«Слово не содержит буквы Ь» при алфавите из шести букв — это слово из оставшихся пяти букв: 5^L вместо 6^L.

А вот условия вида «ровно две буквы Л» или «нет двух одинаковых подряд» через простое произведение не считаются: позиции перестают быть независимыми. Для них есть отдельные приёмы — и есть перебор, который работает всегда.

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

Её легко построить неверно, и ошибку не видно. Забыли, что порядок не важен; не учли, что позиции связаны; перепутали «не более одной» с «ровно одной». Число получается правдоподобное, проверить его нечем.

Условия быстро становятся неформульными. «Цифра 0 не стоит рядом с цифрой 3» — попробуйте свести это к произведению и сочетаниям. Можно, но это отдельная задача минут на двадцать.

Перебор лишён обоих недостатков. Условие переписывается с русского на Python почти дословно, а число вариантов настолько мало, что о времени думать не приходится. Каркас один на все задания:

from itertools import product

alph = 'АДКЛО'

count = 0

for w in product(alph, repeat=6):

word = ''.join(w)

if <условие из задания>:

count += 1

print(count)

product(alph, repeat=6) выдаёт все кортежи длины 6 из букв алфавита, в том числе с повторами, и выдаёт их в лексикографическом порядке, если алфавит отсортирован. Второе свойство понадобится во второй половине урока, когда речь пойдёт о номерах слов.

Вторая половина линии 8 звучит так: «все слова записаны в алфавитном порядке и пронумерованы начиная с 1; под каким номером идёт слово такое-то» — или наоборот, «какое слово стоит под номером N».

За этим стоит точное соответствие.

Отсортируем алфавит по-русски и занумеруем буквы с нуля. Для букв М, А, С, Л, О алфавитный порядок такой: А, Л, М, О, С, и номера: А — 0, Л — 1, М — 2, О — 3, С — 4.

Теперь каждое слово превращается в набор цифр, то есть в число в системе счисления с основанием 5 (размер алфавита). Старшая буква слова — старший разряд числа.

Главное свойство: алфавитный порядок слов в точности совпадает с числовым порядком этих чисел. Оба сравнения идут слева направо и на первом различии дают ответ. Поэтому слово с номером 1 (самое первое) — это ААААА, то есть число 00000, а номер слова равен значению числа плюс один.

Отсюда обе формулы.

Номер по слову. Перевести буквы в цифры, вычислить значение как m-ичного числа, прибавить 1.

Слово по номеру. Вычесть 1, перевести полученное число в m-ичную систему, дополнить нулями слева до нужной длины и заменить цифры буквами. Дополнение нулями обязательно: число 7 в пятеричной системе записывается как «12», но слово длины пять — это «00012», то есть АААЛМ. Без ведущих нулей длина не сойдётся.

Алфавит не отсортирован. В условии буквы перечисляют в произвольном порядке — «М А С Л О», «К О Т», «А Г З О Р». Нумерация же идёт по алфавитному порядку. Строка sorted(...) стоит копейки, а её отсутствие меняет ответ полностью.

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

Основание и показатель наоборот. Слов длины L из m букв — это m^L, а не L^m. Проверяйте себя на маленьком случае: из двух букв слов длины 3 будет 2³ = 8 (ААА, ААБ, АБА, АББ, БАА, БАБ, ББА, БББ) — выпишите и убедитесь.

Три похожих слова, три разных условия. «Ровно», «не более» и «хотя бы» переносятся в код разными знаками: == k, <= k, >= 1. Читайте условие буквально и переносите в код дословно.

Ведущие нули в обратной задаче. Слово имеет фиксированную длину, а число — нет. Дополняйте запись нулями слева до нужной длины, иначе слово выйдет короче.

«Пятизначное число» — это запрет на ноль в начале. В задачах про числа, а не про слова, первый разряд не может быть нулевым, и это уменьшает перебор в m/(m−1) раз.

Слов длины L из алфавита размера m ровно m^L — это правило произведения, применённое к L независимым позициям. Буквы в линии 8 всегда могут повторяться, поэтому ни факториалы, ни перестановки здесь не нужны.

Если на позиции наложено ограничение, число вариантов на ней просто уменьшается: «первая цифра не ноль» даёт 3 · 4⁴ вместо 4⁵. Если ограничение связывает разные позиции — «ровно две буквы Л», «нет двух одинаковых подряд», «ноль не рядом с тройкой», — формулу строить долго и рискованно, и на экзамене надёжнее перебрать всё через itertools.product: вариантов в линии 8 десятки тысяч, компьютер справится мгновенно.

Вторая половина линии 8 держится на одном соответствии: слово из отсортированного алфавита — это число в системе счисления с основанием m, а алфавитный порядок слов совпадает с числовым порядком. Отсюда номер слова равен значению числа плюс один, а слово по номеру получается переводом числа «номер минус один» в m-ичную систему с дополнением нулями слева.

И главная привычка: сортируйте алфавит. Условие перечисляет буквы как попало, нумерация же всегда алфавитная.