Часто в комбинаторных задачах нужно перебрать ВСЕ возможные варианты чего-нибудь. Чаще всего это какой-нибудь комбинаторный объект типа подмножеств, k-ичных чисел, сочетаний или перестановок.
Учебные задачи могут звучать прямо как "переберите все перестановки". Но перебор может помочь решить и какие-нибудь реальные задачи, встречающиеся в олимпиадах.
Например, задачу об укладке N предметов в рюкзак можно решить просто перебором всех подмножеств и выбором самого лучшего из них. Для случая, когда веса предметов - это действительные числа, быстрые полиномиальные решения с динамикой не работают, и надо писать именно перебор.
Подмножество $N$-элементного множества задается маской - строкой из $N$ цифр 0 или 1. Задача перебора всех подмножеств заключается в том, что надо вывести их все, причем в лексикографическом порядке.
Это можно делать двумя способами. Первый - это заметить, что достаточно просто вывести все числа от $0$ до $2^N - 1$ в двоичном формате.
Кстати, выводить числа в двоичном формате очень просто, так как числа хранятся в компьютере уже в двоичном формате. Очень удобно воспользоваться двоичными операциями. Например, $x << y$ возвращает число $x$, которое в двоичном формате сдвинули вправо на $y$ битов. То есть у него появилось справа $y$ нулей. Можно сказать, что $x << y = x 2^y$. Поэтому часто пишут $1 << n$, это значит $2^n$, и работает гораздо гораздо быстрее, чем обычное возведение в степень.
А как вывести двоичное представление числа $x$? А именно как узнать $i$-ый справа бит числа $x$? Можно воспользоваться логической операцией И ($\&$). Она берет два числа, и возвращает число, у которого $i$-ый бит равен 1, если оба $i$-ых бита этих чисел равны 1, а иначе 0.
Тогда $i$-ый бит числа $x$ можно извлечь благодаря операции $x \& (2^i)$. Если он равен 1, то эта операция вернет число $2^i$, а иначе она вернет $0$.
n = 3
for subset in range(2 ** n):
for bit in range(n):
if subset & 1 << bit:
print(1, end = '')
else:
print(0, end = '')
print()
Но есть и второй способ - более общий, и им мы будем пользоваться для всех задач перебора. Идея состоит в вызове рекурсивной функции gen.
У функции gen есть два аргумента
def gen(n, prefix=[]):
if len(prefix) == n:
print(''.join(prefix))
return
prefix.append('0')
gen(n, prefix)
prefix.pop()
prefix.append('1')
gen(n, prefix)
prefix.pop()
gen(3)
# или так
def gen(n, prefix_len=0, prefix=['0'] * n):
if prefix_len == n:
print(''.join(prefix))
return
prefix[prefix_len] = '0'
gen(n, prefix_len + 1, prefix)
prefix[prefix_len] = '1'
gen(n, prefix_len + 1, prefix)
gen(3)
Обратите внимание, как это работает: функция gen(n, prefix) перебирает, чему равен символ, следующий после prefix - либо 0, либо 1. Оба эти варианта возможны, и для них обоих нужно сгенерировать и вывести все возможные продолжения этого префикса.
Почему получилось вывести все подмножества в лексикографическом порядке? Потому что на каждом шаге мы сначала рассматривали случай, когда символ равен 0, и выводили все такие подмножества, а потом уже случай, когда он равен 1. Чтобы вывести все те же множества в обратном лексикографичеспорядком порядке, надо поменять местами вызовы для 0 и 1.
Пусть, нам требуется перебрать все $k$-ичные числа длины $n$. Например, это может быть нужно в переборе, где каждый из $n$ объектов может принимать любое из $k$ состояний.
Это несложное усложнение предыдущей задачи. И ее тоже можно решать двумя способами. Первый - это просто перебрать числа от $0$ до $k^n - 1$ и вывести их в $k$-ичной форме.
Второй - это применить рекурсивную функцию. Будем генерировать цифры числа по одной, перебирая все возможные варианты.
n = 2
k = 3
def gen(n, k, prefix=[]):
if len(prefix) == n:
print(''.join(prefix))
return
for i in range(k):
prefix.append(str(i))
gen(n, k, prefix)
prefix.pop()
gen(n, k)
Теперь мы хотим перебрать все перестановки длины $N$, тоже в лексикографическом порядке.
Первый способ с циклом по двоичным числам тут уже не сработает. Но второй способ прекрасно обобщается. Будем делать абсолютно так же, перебирать все время новую цифру. Но появляется особенность - нельзя выбирать цифру, которая уже встречалась в перестановке ранее. Для удобства будем хранить массив bool-ов used.
n = 4
used = [False] * n
def gen(n, used, prefix=[]):
if len(prefix) == n:
print(''.join(prefix))
return
for i in range(n):
if not used[i]:
used[i] = True
prefix.append(str(i))
gen(n, used, prefix)
used[i] = False
prefix.pop()
gen(n, used)
Сочетания из $n$ по $k$ удобно представить как отсортированный набор из $k$ разных чисел от $1$ до $n$. Интересно их тоже все вывести в лексикографическом порядке. Для $n = 5, k = 3$ это сочетания от $1 2 3$ до $3 4 5$.
Эту задачу можно решить с помощью нашего рекурсивного подхода, но надо делать это аккуратно и не перебирать ни в какой момент лишние сочетания.
Но давайте вместо этого рассмотрим другой, новый подход. Давайте научимся генерировать следующее сочетание в смысле лексикографического порядке на основе текущего. Это тоже делается примерно одним и тем же способом всегда.
Первым сочетанием, возьмем просто числа от $1$ до $k$. Пусть теперь мы зафиксировали текущее сочетание.
Надо увеличивать последний элемент, который мы еще можем увеличить, а всем последующим присвоить минимальные возможные значения. Если увеличить ничего нельзя, то полученное сочетание – максимальное. Когда элемент на позиции $i$ (считая с 0) можно увеличить? Когда существуют хотя бы $k-i$ чисел больше текущего, чтобы можно было поставить их после него.
n = 5
k = 3
# самое первое сочетание
combination = [i+1 for i in range(k)]
def next_combination(combination):
# изменяет массив на следующее лексикографически сочетание
for i in range(k - 1, -1, -1):
if combination[i] <= n - k + i:
combination[i] += 1
for j in range(i + 1, k):
combination[j] = combination[j - 1] + 1
return True
return False
print(combination)
while next_combination(combination):
print(combination)
Кроме того, такой подход подойдет для генерации лексикографически следующей комбинации рассмотренных раньше типов. Так у $k$-ичного числа можно находить последнюю цифру, не равную $k-1$, увеличивать ее, а все последующие заменить на 0. Аналогично с генерацией подмножеств.
Разумеется, многое из этого уже было написано. Так, в C++, есть функция std::next_permutation, которая делает из перестановки следующую, а в питоне есть модуль itertools, который содержит несколько полезных функций.
from itertools import product, combinations, permutations
print("k-ичные числа")
for i in product('012', repeat=2):
print(''.join(i))
print("Перестановки")
for i in permutations('012', 3):
print(''.join(i))
print("Сочетания")
for i in combinations([1,2,3,4], 3):
print(i)