Часто в комбинаторных задачах нужно перебрать ВСЕ возможные варианты чего-нибудь. Чаще всего это какой-нибудь комбинаторный объект типа подмножеств, 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()000
100
010
110
001
101
011
111Но есть и второй способ - более общий, и им мы будем пользоваться для всех задач перебора. Идея состоит в вызове рекурсивной функции gen.
У функции gen есть два аргумента * n - это финальная длина подмножества * prefix - это ссылка на список/вектор с уже сгенерированным префиксом подмножества
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)000
001
010
011
100
101
110
111# или так
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)000
001
010
011
100
101
110
111Обратите внимание, как это работает: функция 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)00
01
02
10
11
12
20
21
22Теперь мы хотим перебрать все перестановки длины \(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)0123
0132
0213
0231
0312
0321
1023
1032
1203
1230
1302
1320
2013
2031
2103
2130
2301
2310
3012
3021
3102
3120
3201
3210Сочетания из \(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)[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]Кроме того, такой подход подойдет для генерации лексикографически следующей комбинации рассмотренных раньше типов. Так у \(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)k-ичные числа
00
01
02
10
11
12
20
21
22
Перестановки
012
021
102
120
201
210
Сочетания
(1, 2, 3)
(1, 2, 4)
(1, 3, 4)
(2, 3, 4)