Перебор

product: всё со всем

Вспомни цикл в цикле из темы 3. Если нужно перебрать все слова из трёх букв алфавита АБ, можно написать три вложенных цикла:

for a in 'АБ':
    for b in 'АБ':
        for c in 'АБ':
            print(a + b + c)

А если длина слова 8? Восемь вложенных циклов писать никто не будет. Для этого есть product из модуля itertools: длину задаём через repeat.

from itertools import product

for x in product('АБ', repeat=3):
    print(x, ''.join(x))

product выдаёт каждое слово как набор в круглых скобках, это называется кортеж. Склеиваем его в строку через ''.join(x) из темы 4. Порядок слов тот же, что у вложенных циклов: если буквы в строке по алфавиту, то и слова идут по алфавиту.

Буквы могут повторяться, поэтому слов 2 · 2 · 2 = 8. В общем случае число букв в степени длины.

permutations: без повторов

permutations переставляет элементы местами, и каждый используется не больше одного раза. Без второго аргумента берёт все элементы:

from itertools import permutations

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

Шесть перестановок: 3 · 2 · 1. Если нужны не все элементы, а только r штук, пишем r:

from itertools import permutations

k = 0
for x in permutations('012345', r=3):      # трёхзначные из цифр 0–5, все разные
    if x[0] != '0':
        k += 1
print(k)

combinations: выбор без порядка

combinations выбирает r элементов, но порядок не важен: АБ и БА это один и тот же выбор.

from itertools import combinations, permutations

print(list(combinations('АБВГ', 2)))
print(len(list(combinations('АБВГ', 2))), len(list(permutations('АБВГ', 2))))

Шесть выборов против двенадцати перестановок: каждая пара в permutations встречается дважды, в обоих порядках.

На ЕГЭ combinations нужна реже двух других, но выручает в задачах вида «выбрать несколько чисел с условием»:

from itertools import combinations

# способы выбрать три разных числа от 1 до 10 с суммой 15
for c in combinations(range(1, 11), 3):
    if sum(c) == 15:
        print(c)

Как выбрать

Подсказки из условия:

• «буквы могут повторяться» или ничего не сказано про повторы: product;
• «все буквы различны», «переставляя буквы слова»: permutations;
• «выбрать несколько» и порядок не важен: combinations.

Если сомневаешься, бери product и проверяй ограничения в if. Он подходит почти всегда, просто перебирает больше.

Сломай код

TypeError: забыли repeat

from itertools import product

for x in product('АБ', 3):
    print(x)

'int' object is not iterable. Без repeat= число 3 воспринимается как второй набор букв, а по числу перебирать нельзя. Пиши repeat=3.

Тихая ошибка: забыли join

from itertools import product

k = 0
for x in product('АБ', repeat=2):
    if x == 'АБ':
        k += 1
print(k)

Слово АБ точно есть, а счётчик 0. x это кортеж ('А', 'Б'), а не строка 'АБ', и они не равны. Первой строкой в цикле x = ''.join(x).

Тихая ошибка: повторы в permutations

from itertools import permutations

print(len(list(permutations('ААБ'))))
print(len(set(permutations('ААБ'))))

Различных слов из букв ААБ три (ААБ, АБА, БАА), а permutations выдал шесть: для него две буквы А разные. set убирает одинаковые. Подробно с примерами это в уроке №8.

Где пригодится на ЕГЭ

Как выглядит №2. Все строки таблицы истинности для четырёх переменных это все наборы из нулей и единиц длины 4. Их как раз даёт product:

from itertools import product

print('x y z w')
for x, y, z, w in product([0, 1], repeat=4):
    F = ((x <= y) and (y == z)) or w
    if F:
        print(x, y, z, w)

x, y, z, w = ... раскладывает набор по четырём переменным, как a, b = ... в теме 9. Следование → записано через <=, равносильность ≡ через ==.