Комбинаторика

Что проверяет номер

В №8 из заданных букв или цифр составляют все возможные слова или числа, а потом что-то про них спрашивают. Задачи бывают двух видов, и их полезно различать с первого взгляда.

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

Можно ли решить руками? Можно, через формулы комбинаторики. Но на экзамене это долго, и легко упустить один случай. Руками мы будем считать только маленькие примеры, чтобы понимать, что делает код.

База: перебор, номер и счётчик

Тут четыре вещи, на которых держится любое решение №8. Если они понятны, дальше будут только разные условия в if.

1. product: все слова, буквы могут повторяться

Функция product из модуля itertools выдаёт все слова заданной длины из заданных букв. Длину пишем через repeat.

from itertools import product

for x in product('АБ', repeat=2):
    print(x)

Получили все 4 слова из букв А и Б длины 2. Обрати внимание на порядок: если буквы в строке записаны по алфавиту, то и слова идут по алфавиту. Это пригодится в задачах «по порядку».

2. join: склеиваем слово в строку

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

from itertools import product

for x in product('АБ', repeat=3):
    x = ''.join(x)   # ('А', 'Б', 'А') превращается в 'АБА'
    print(x)

В кавычках перед join стоит то, чем разделять буквы. В №8 разделитель не нужен, поэтому кавычки всегда пустые.

3. permutations: каждая буква только один раз

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

from itertools import permutations

for x in permutations('КОТ'):
    print(''.join(x))

# а теперь слова из двух букв
for x in permutations('КОТ', r=2):
    print(''.join(x))

Как выбрать между ними:

Если сомневаешься, бери product. Он подходит почти всегда, а «все буквы разные» можно проверить отдельным условием.

4. Номер слова и количество слов

Это две разные переменные, и их часто путают.

• Номер n растёт на каждом слове, подходит оно или нет. Так мы знаем, какое по счёту слово сейчас проверяем.
• Счётчик k растёт только внутри if, когда слово подошло. Так мы считаем подходящие.

from itertools import product

n = 0   # номер слова
k = 0   # сколько слов подошло
for x in product('КОТ', repeat=3):
    x = ''.join(x)
    n += 1              # каждое слово получает свой номер

    if x == 'ТОК':
        print('Номер ТОК:', n)

    if x.count('О') == 1:
        k += 1          # считаем только подходящие

print('Слов ровно с одной О:', k)

Заметь, где стоит print(k): после цикла, без отступа. Если поставить его внутрь, он напечатается 27 раз, и ответом будет только последняя строка. Попробуй: сдвинь последнюю строку на 4 пробела вправо и запусти.

Слова по порядку

Это задачи, где слова выписаны по алфавиту и пронумерованы. Шаблон тот же, что в разделе 2: перебираем, склеиваем, ведём номер. Ошибаются тут в трёх местах: в порядке букв, в выборе первого или последнего слова и в том, какие слова нумеруют.

Буквы должны идти по алфавиту

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

• переписать их руками: 'ИЛСТ';
• отсортировать: sorted('ЛИСТ') даст те же И, Л, С, Т.

Если в слове из условия буквы повторяются, например «ПАПА», повторы надо убрать, иначе слова будут дублироваться: sorted(set('ПАПА')).

Первое или последнее слово

• Последнее подходящее: печатаем номер каждого подходящего слова, ответ это последняя строка вывода.
• Первое подходящее: печатаем номер и сразу останавливаем цикл командой break.

Пример. Слова длины 5 из букв слова ЛИСТ выписаны по алфавиту. Под каким номером стоит последнее слово с чётным номером, которое не начинается с Т и содержит ровно две буквы И?

from itertools import product

n = 0
for x in product(sorted('ЛИСТ'), repeat=5):
    x = ''.join(x)
    n += 1
    # чётный номер, первая буква не Т, ровно две И
    if n % 2 == 0 and x[0] != 'Т' and x.count('И') == 2:
        print(n, x)

Вывод длинный, нужна только последняя строка: 708 СТИИТ. Слово рядом с номером печатаем, чтобы глазами проверить, что условие записано правильно. Это хорошая привычка.

Когда нумеруют не все слова

Иногда в условии сказано, что пронумерованы только слова с каким-то свойством, например «без двух одинаковых букв подряд». Тогда n += 1 переезжает внутрь if: номер получают только подходящие слова.

from itertools import product

n = 0
for x in product('АБВ', repeat=4):
    x = ''.join(x)
    # нумеруем только слова без двух одинаковых букв подряд
    if 'АА' not in x and 'ББ' not in x and 'ВВ' not in x:
        n += 1
        if x == 'ВАБА':
            print(n)

Сколько слов с условием

Здесь списка нет, нужно посчитать подходящие слова. Работает счётчик k, и почти всё решение сводится к тому, чтобы правильно записать условие в if. Ниже проверки, которые встречаются чаще всего.

Две проверки стоит разобрать.

Все буквы разные. set(x) убирает повторы. Если после этого длина не изменилась, повторов не было.

Сколько гласных. x.count('Е') + x.count('О') работает, но если гласных пять, строка выйдет длинной. Запись sum(x.count(c) for c in 'ЕО') делает то же самое: считает каждую букву из списка и складывает.

Пример. Сколько слов длины 5 можно составить из букв слова ПЕСОК, если слово начинается с согласной, заканчивается гласной и все буквы в нём разные?

from itertools import product

k = 0
for x in product('ПЕСОК', repeat=5):
    x = ''.join(x)
    if x[0] not in 'ЕО' and x[-1] in 'ЕО' and len(set(x)) == len(x):
        k += 1
print(k)

Ответ 36. Руками: первая согласная (П, С или К) выбирается 3 способами, последняя гласная 2 способами, оставшиеся три буквы расставляются на три места 3 · 2 · 1 = 6 способами. Итого 3 · 2 · 6 = 36.

«Можно получить перестановкой букв слова»

Такая формулировка путает: кажется, что нужен permutations. На самом деле она значит, что в слове те же буквы в том же количестве, просто в другом порядке. Проще всего это проверить так: если отсортировать буквы обоих слов, получится одно и то же.

from itertools import product

k = 0
for x in product('АМР', repeat=4):
    x = ''.join(x)
    # те же буквы, что в слове РАМА, в любом порядке
    if sorted(x) == sorted('РАМА'):
        k += 1
print(k)

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

Вместо слов тут числа: «сколько пятизначных восьмеричных чисел…». Для Python это те же слова, только буквы теперь цифры. Нового тут три вещи.

1. Цифры системы счисления

Для восьмеричной системы цифры это '01234567'. Для системы больше десяти после 9 идут буквы: в шестнадцатеричной это 0–9 и a–f. Чтобы не выписывать их руками, есть готовая строка:

from string import printable

print(printable[:8])    # цифры восьмеричной системы
print(printable[:16])   # цифры шестнадцатеричной

Буквы в printable маленькие: a, b, c. Если в проверках пишешь цифру-букву, пиши её тоже маленькой.

2. Число не начинается с нуля

product об этом не знает и спокойно составит 00123. Это уже не пятизначное число, поэтому в каждой задаче на числа первая проверка x[0] != '0'.

3. Чётные и нечётные цифры

Если цифр мало, их можно перечислить: нечётные восьмеричные это '1357'. Для любой системы работает перевод цифры в число: int(c, 16) переводит шестнадцатеричную цифру c в обычное число, а дальше проверяем остаток от деления на 2.

Пример. Сколько существует пятизначных восьмеричных чисел, в которых ровно одна цифра 7 и не больше двух цифр, больших 4?

from itertools import product
from string import printable

k = 0
for x in product(printable[:8], repeat=5):
    x = ''.join(x)
    if x[0] != '0' and x.count('7') == 1 and sum(x.count(c) for c in '567') <= 2:
        k += 1
print(k)

А так считаются нечётные цифры в любой системе. Например, четырёхзначные шестеричные числа ровно с двумя нечётными цифрами:

from itertools import product
from string import printable

k = 0
for x in product(printable[:6], repeat=4):
    x = ''.join(x)
    odd = [c for c in x if int(c, 6) % 2 == 1]   # все нечётные цифры числа
    if x[0] != '0' and len(odd) == 2:
        k += 1
print(k)

Если в условии сказано «все цифры различны», бери permutations с длиной r: повторов не будет сразу, отдельно проверять не нужно.

Соседи: приём с заменой

Частое условие: «никакие две нечётные цифры не стоят рядом» или «нечётная цифра не стоит рядом с 7». Проверять каждую пару соседей вручную долго. Есть приём короче.

Идея

Сделаем копию числа и заменим в ней все нечётные цифры на одну и ту же, например на 1. Число 152063 превратится в 112061. Теперь «две нечётные рядом» это просто '11' в строке. Какие именно цифры там стояли, уже неважно.

Пример. Сколько существует шестизначных чисел в семеричной системе, в которых никакие две нечётные цифры не стоят рядом?

from itertools import product
from string import printable

k = 0
for x in product(printable[:7], repeat=6):
    x = ''.join(x)
    x1 = x                        # копия, исходное число не портим
    for c in '35':
        x1 = x1.replace(c, '1')   # все нечётные превращаем в 1
    if x[0] != '0' and '11' not in x1:
        k += 1
print(k)

Ответ 43728. Тройку и пятёрку заменили на единицу, а сама единица и так единица.

Почему заменяем в копии, а не в самом x? Исходное число ещё нужно: проверить, что оно не начинается с нуля, а иногда и вывести его в ответ. После замен по x1 уже не понять, какое число было.

Чётные и нечётные сразу

«Никакие две чётные и никакие две нечётные не стоят рядом»: заменяем нечётные на 1, чётные на 2 и проверяем две строки.

for c in '1357':
    x1 = x1.replace(c, '1')
for c in '02468':
    x1 = x1.replace(c, '2')
if '11' not in x1 and '22' not in x1:
    ...

Нечётная рядом с конкретной цифрой

«Ни одна нечётная цифра не стоит рядом с 7» в восьмеричной системе. Семёрку не заменяем, остальные нечётные превращаем в 1. Плохие соседи тогда 17, 71 и 77.

from itertools import product
from string import printable

k = 0
for x in product(printable[:8], repeat=5):
    x = ''.join(x)
    x1 = x
    for c in '35':
        x1 = x1.replace(c, '1')   # все нечётные, кроме 7, в 1
    if x[0] != '0' and '17' not in x1 and '71' not in x1 and '77' not in x1:
        k += 1
print(k)

Запасной способ: список плохих пар

Если приём с заменой не придумывается, можно выписать все запрещённые пары и проверить, что ни одной нет в числе:

bad = [a + b for a in '135' for b in '135']   # 11, 13, 15, 31, ... все пары нечётных
if all(p not in x for p in bad):
    ...

all(...) вернёт True, только если каждая проверка внутри True. Ответ получится тот же, просто замена короче и в ней проще не ошибиться.

Перестановки букв слова

«Вася составляет слова, переставляя буквы слова КАРТА». Тут нужен permutations: буквы только переставляются, новых не появляется. Но есть подвох.

Повторяющиеся буквы

В слове КАРТА две буквы А. Для Python это разные элементы: первая А и вторая А. Если их поменять местами, Python посчитает это новым словом, хотя для нас слово то же самое.

from itertools import permutations

print(len(list(permutations('КАРТА'))))   # с повторами
print(len(set(permutations('КАРТА'))))    # различные слова

set убирает одинаковые слова, и остаются 60 различных. Если в слове есть повторяющиеся буквы, set нужен обязательно.

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

from itertools import permutations

k = 0
for x in set(permutations('БАНАН')):
    x = ''.join(x)
    if 'НН' not in x:
        k += 1
print(k)

Ответ 18. Проверим руками: всего различных слов 5! / (2! · 2!) = 30. Если склеить НН в один блок, останется переставить 4 элемента с двумя А: 4! / 2! = 12. Значит, без НН рядом 30 − 12 = 18.

Ловушка с count

«Ровно один раз встречаются две гласные подряд». Хочется заменить все гласные на одну букву и проверить count('ГГ') == 1. Но count считает вхождения, которые не пересекаются:

print('ГГГ'.count('ГГ'))

В «ГГГ» две пары гласных подряд (первая со второй и вторая с третьей), а count насчитает одну. Поэтому добавляем проверку, что трёх гласных подряд нет.

from itertools import permutations

k = 0
for x in set(permutations('КАКАО')):
    x = ''.join(x)
    x1 = x
    for c in 'АО':
        x1 = x1.replace(c, 'Г')   # все гласные в одну букву
    # ровно одна пара гласных подряд и нет трёх подряд
    if x1.count('ГГ') == 1 and 'ГГГ' not in x1:
        k += 1
print(k)

Ответ 18. Без проверки на 'ГГГ' получилось бы 27, и это была бы ошибка.

Ловушки перед экзаменом

Всё, на чём теряют балл в №8, одним списком. Пробеги глазами перед пробником.

Как проверить себя за 30 секунд

Перед тем как вписать ответ, выведи рядом с номером или вместо счётчика сами слова: print(n, x) или print(x). Посмотри на последние несколько. Если глазами видно, что слово не подходит под условие, значит, в if ошибка. Это ловит большинство ошибок из таблицы выше.