Python: перебор сочетаний с itertools.product

Если каждая логическая переменная может быть нулём или единицей, все значения функции можно проверить перебором. Для двух переменных нужны четыре пары, для трёх — восемь троек. Функция product из модуля itertools создаёт такие сочетания и позволяет записать перебор без нескольких вложенных циклов.

От двух циклов к одной строке

Сначала фиксируется значение x, затем для него перебираются оба значения y. Внутренний цикл полностью выполняется при каждом новом значении внешнего:

for x in (0, 1):
    for y in (0, 1):
        print(x, y)

Получаются пары 0 0, 0 1, 1 0, 1 1. Вызов product строит их в том же порядке: правая позиция меняется быстрее левой.

from itertools import (
    product,
)

bits = (0, 1)
for x, y in product(
    bits, bits
):
    print(x, y)

Импорт выполняется до использования функции. Каждый аргумент product задаёт возможные значения своей позиции. Например, product((1, 2), (7, 8)) выдаёт (1, 7), (1, 8), (2, 7), (2, 8). Значения разных позиций не обязаны различаться.

Что означает repeat

Когда набор возможных значений одинаков, его можно передать один раз и указать число позиций. Запись product(bits, repeat=3) соответствует трём вложенным циклам по bits. Это не повторение каждого готового результата трижды.

for x, y, z in product(
    bits, repeat=3
):
    print(x, y, z)

У каждой из трёх позиций по два варианта, поэтому получается 2^3=8 троек: от 0 0 0 до 1 1 1. При repeat=4 будет 2^4=16 четвёрок. Увеличение числа переменных на одну удваивает перебор; короткая запись не уменьшает количество проверяемых наборов.

Кортеж и распаковка

Один результат product — кортеж. Его можно получить целиком, а затем распределить значения по переменным:

row = (0, 1, 0)
x, y, z = row

Такое распределение называется распаковкой: теперь x равно нулю, y единице, z нулю. В заголовке цикла for x, y, z in ... распаковка происходит для каждого кортежа. Число переменных должно соответствовать числу позиций: тройку нельзя распаковать в четыре переменные.

Отбор по настоящей формуле задания №2

В задаче с неизвестными столбцами ↗ дана функция F=((z\to x)\to(x\equiv y))\lor\neg w. Требуются наборы с F=0. Сначала обозначаются внутренние части: A соответствует z\to x, B — x\equiv y. Импликация записывается через отрицание и ИЛИ, эквивалентность — сравнением.

from itertools import (
    product,
)

bits = (0, 1)
for x, y, z, w in product(
    bits, repeat=4
):
    A = (not z) or x
    B = x == y
    F = (
        (not A) or B
        or (not w)
    )
    if not F:
        print(x, y, z, w)

В каждом проходе используются все четыре значения одного набора. Сначала вычисляются части формулы, затем весь результат. Условие if not F пропускает к печати только ложный результат. Вывод в выбранном порядке x,y,z,w:

0 1 0 1
1 0 0 1
1 0 1 1

Слова True и False обозначают логические значения. Операции and и or могут вернуть также исходные ноль или единицу; для этого перебора проверка истинности остаётся верной. Если требуется напечатать результат именно цифрой, используется int(bool(F)); для отбора истинных наборов — if F:.

Возможные ловушки

Повторно обходить уже использованный результат. product возвращает итератор. После полного цикла он исчерпан. Для нового прохода создаётся новый product либо результаты заранее сохраняются через list. Входные наборы должны быть конечными: функция сначала запоминает их значения.

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

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

Устройство функции сверено с официальным описанием itertools.product ↗.