Измерение количества информации

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

«Все пятибуквенные слова, составленные из букв Т, О, Р, К, А, записаны в алфавитном порядке и пронумерованы, начиная с 1. Сколько слов с нечётными номерами не начинаются с буквы А, содержат ровно две буквы О и не содержат двух букв О подряд?»

Каждое ограничение превращают в отдельное правило, а слова считают рассуждением или перебирают программой. Сначала разберём, что сказано в условии:

Тема состоит из шести подтем — у каждой своя страница. Идём по ним по порядку:

1. Слова и перебор — ты сейчас здесь.
2. Сколько раз встречается буква — «ровно две О», «хотя бы одна», «не более».
3. Соседние буквы — условия вида «нет двух О подряд».
4. Числа в системе счисления — когда слово — это запись числа.
5. Нумерованный список — номер слова по алфавиту и ответ задачи темы: 168.
6. Когда перебор не успевает — дополнительный урок для очень длинных слов.

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

Слово здесь — любая последовательность букв, смысл не важен, а порядок важен. КОТ и ТОК — разные слова; ООАКР — тоже слово.

Набор разрешённых букв называют алфавитом. В задаче темы алфавит — пять букв Т, О, Р, К, А, длина слова — 5. Если не сказано иное, буквы могут повторяться.

«Из букв слова КОЛОС» значит алфавит из различных букв К, О, Л, С. А «переставить все буквы слова КОЛОС» — другое условие: каждую букву нужно использовать столько раз, сколько она встречается (подтема 2).

Число слов находят умножением: на каждом месте выбор разветвляется. Двухсимвольный код, где первый символ — А или Б, а второй — 0, 1 или 2, имеет 2 · 3 = 6 вариантов:

Пятибуквенных слов из Т, О, Р, К, А — 5 · 5 · 5 · 5 · 5 = 5⁵ = 3125. Ограничение на одно место меняет только его множитель: слов, которые не начинаются с А, 4 · 5⁴ = 2500.

Непересекающиеся случаи складывают; если случаи пересекаются, общие слова вычитают один раз. Слов длины 2 или 3 из пяти букв — 5² + 5³ = 150: слово не может иметь сразу две длины.

А трёхбуквенных слов из АОБВГ, которые начинаются с А или заканчиваются на А, не 25 + 25: пять слов вида А?А попали в оба случая.

Если буквы не повторяются, каждый следующий множитель на единицу меньше. Трёхбуквенных слов из пяти букв без повторений 5 · 4 · 3 = 60: какие бы буквы ни выбрали раньше, вариантов всегда на одну меньше.

Переставить все пять различных букв можно 5 · 4 · 3 · 2 · 1 = 120 способами. Такое произведение записывают как 5! («пять факториал»).

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

for first in 'АБ':    for second in '012':        print(first + second)

Для пяти мест вместо пяти вложенных циклов берут функцию product из модуля itertools: product('АКОРТ', repeat=5) выдаёт все наборы из пяти букв по очереди. ''.join(letters) склеивает набор в строку, а счётчик растёт на каждом подходящем слове:

from itertools import product count = 0for letters in product('АКОРТ', repeat=5):    word = ''.join(letters)    if word[0] != 'А':        count += 1print(count)

Программа дала то же 2500, что и умножение. Первая буква — word[0], последняя — word[-1].

Слова без повторений перебирает permutations из того же модуля:

from itertools import permutations print(len(list(permutations('АОБВГ', 3))))

• Словопоследовательность букв; порядок важен
• Умножениеmⁿ слов длины n из m букв
• Сложениенепересекающиеся случаи; общие вычесть один раз
• Без повторов5 · 4 · 3; все n букв — n!
• productперебор всех слов, проверка, счётчик