Когда перебор не успевает

Для слов длины 20 перебор уже не успевает: вариантов больше триллиона. Пятибуквенных слов из АБВГ всего 4⁵ = 1024, и перебор с проверкой 'АА' not in word даёт ответ мгновенно. Но для длины 20 вариантов 4²⁰ — больше триллиона.

Нужен способ, в котором число шагов не растёт вместе с числом слов.

Чтобы понять, можно ли дописать букву, не нужно знать всё слово. Для запрета АА достаточно знать, заканчивается ли слово на А. Разделим допустимые слова текущей длины на две группы: a — заканчиваются на А, b — на другую букву.

При дописывании буквы новые слова на А получаются только из группы b: a_новое = b. Новые слова на другую букву — из любой группы, и последних букв три: b_новое = 3 · (a + b). Для длины 1 a = 1, b = 3.

Для длины 5 получаем 171 + 648 = 819 — столько же даёт перебор. Для длины 20 меняется одно число в range:

end_a = 1end_other = 3for length in range(2, 21):    new_a = end_other    new_other = 3 * (end_a + end_other)    end_a = new_a    end_other = new_other print(end_a + end_other)

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

Если важны только типы цифр, перебирают схемы типов, а не сами цифры. Посчитаем двенадцатизначные восьмеричные числа, в записи которых ровно четыре нечётные цифры и никакие две нечётные не стоят рядом. Самих чисел около 6 · 10¹⁰ — перебор не успеет.

Схема — на каждом месте «ч» или «н», их всего 2¹² = 4096. Для подходящей схемы число чисел даёт умножение: нечётная цифра — 4 варианта, чётная — 4, но на первом месте чётная не может быть нулём — 3.

from itertools import product def by_types(length, odd_count):    total = 0    for types in product('чн', repeat=length):        scheme = ''.join(types)        if scheme.count('н') != odd_count:            continue        if 'нн' in scheme:            continue        ways = 1        for i, kind in enumerate(scheme):            if kind == 'н':                ways *= 4            elif i == 0:                ways *= 3            else:                ways *= 4        total += ways    return total brute = 0for d in product(range(8), repeat=5):    odd = [x % 2 for x in d]    if d[0] != 0 and sum(odd) == 2:        if all(odd[i] + odd[i + 1] < 2 for i in range(4)):            brute += 1 print(by_types(5, 2), brute)print(by_types(12, 4))

Сначала способ проверен на пятизначных числах, где перебор ещё возможен, затем та же функция by_types считает двенадцатизначные.

• Оценкаmⁿ вариантов; от миллиардов — не успеть
• Состоянияхранить количества по тому, что нужно для продолжения
• Схемы типовперебрать схемы, каждую посчитать умножением
• Проверкасверить способ с перебором на малых длинах