Слово и номер

Слова выписали в столбик по алфавиту

Второй большой тип задания 8. Все слова заданной длины расставили по алфавиту и пронумеровали с единицы. Спрашивают либо какое слово стоит на N-м месте, либо какой номер у данного слова.

Список длинный — для трёх букв и длины 5 это уже 243 слова. Выписывать нельзя. Но у списка есть скрытая структура, и она превращает задачу в арифметику.

Это счёт в другой системе счисления

Посмотри на список внимательно: последняя буква меняется чаще всех, предпоследняя — реже, первая — реже всех. Точно так же ведут себя цифры при обычном счёте.

Замени буквы цифрами по порядку алфавита — и список станет обычным счётом, только основание равно числу букв.

Слово №1 — это число 0.
Значит слово №100 — это число 99, записанное в троичной системе: 99 = 10200. Читаем цифры как буквы: 1→О, 0→А, 2→У, 0→А, 0→А, получается ОАУАА.

Обратная задача: номер по слову

Дано слово — найти номер. Идём в другую сторону: буквы переводим в цифры, читаем как число, прибавляем 1. 

Слово ОУАОУ при А=0, О=1, У=2 даёт цифры 1, 2, 0, 1, 2. Считаем в троичной: 1·81 + 2·27 + 0·9 + 1·3 + 2 = 140. Номер = 140 + 1 = 141.

Единица здесь не украшение: нумерация начинается с 1, а счёт чисел — с 0. Об эту разницу спотыкаются чаще всего.

Программное решение

Перевод в троичную и обратно руками работает, но в нём две ловушки. Первая: буквы в условии часто перечислены не по алфавиту, и если присвоить цифры в порядке условия, всё поедет. Вторая: та самая разница между позицией (счёт с нуля) и номером (счёт с единицы).

Какую задачу решает код: построить весь список слов в алфавитном порядке. Как только список есть, обе задачи решаются одной строкой каждая — переводить ничего не надо.

Разберём по частям. product("АОУ", repeat=5) выдаёт все цепочки длины 5. "".join(w) склеивает кортеж букв в слово. sorted расставляет слова по алфавиту — ровно так, как описано в условии. После этого sp[99] — слово №100 (индекс на единицу меньше номера), а sp.index("ОУАОУ") + 1 — номер слова.

Почему это надёжнее формул: список строится по тому же правилу, которое написано в задании, поэтому ошибиться в нём попросту негде. 243 слова — мелочь для компьютера; даже 6 букв при длине 6 (это около 47 тысяч слов) он отсортирует мгновенно. На экзамене такие задания решают именно так.

Результат

ОАУАА
141

Обе величины сошлись с ручным счётом. Держи в голове главное правило этого типа: индекс в списке на единицу меньше номера в задании. Почти все ошибки здесь — ровно на эту единицу.

Проверь себя