Часто в комбинаторных задачах нужно перебрать ВСЕ возможные варианты чего-нибудь. Чаще всего это какой-нибудь комбинаторный объект типа подмножеств, k-ичных чисел, сочетаний или перестановок.
Учебные задачи могут звучать прямо как "переберите все перестановки". Но перебор может помочь решить и какие-нибудь реальные задачи, встречающиеся в олимпиадах.
Например, задачу об укладке N предметов в рюкзак можно решить просто перебором всех подмножеств и выбором самого лучшего из них. Для случая, когда веса предметов - это действительные числа, быстрые полиномиальные решения с динамикой не работают, и надо писать именно перебор.
Подмножество
Это можно делать двумя способами. Первый - это заметить, что достаточно просто вывести все числа от
Кстати, выводить числа в двоичном формате очень просто, так как числа хранятся в компьютере уже в двоичном формате. Очень удобно воспользоваться двоичными операциями. Например,
А как вывести двоичное представление числа
Тогда
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.
Пусть, нам требуется перебрать все
Это несложное усложнение предыдущей задачи. И ее тоже можно решать двумя способами. Первый - это просто перебрать числа от
Второй - это применить рекурсивную функцию. Будем генерировать цифры числа по одной, перебирая все возможные варианты.
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
Теперь мы хотим перебрать все перестановки длины
Первый способ с циклом по двоичным числам тут уже не сработает. Но второй способ прекрасно обобщается. Будем делать абсолютно так же, перебирать все время новую цифру. Но появляется особенность - нельзя выбирать цифру, которая уже встречалась в перестановке ранее. Для удобства будем хранить массив 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 = 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]
Кроме того, такой подход подойдет для генерации лексикографически следующей комбинации рассмотренных раньше типов. Так у
Разумеется, многое из этого уже было написано. Так, в 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)