В различных задачах оптимизации частенько приходится перебирать все возможные варианты, в частности все возможные подмножества заданного множества. В этой задаче всего
комбинаций, где
— мощность множества. Простейший алгоритм перебора тесно связан с двоичным разложением номера перебираемой комбинации. Например:
__123
0_000
1_100
2_010
3_110
4_001
5_101
6_011
7_111Здесь в первой строке записаны номера элементов множества (которое состоит из трёх элементов), в следующих строках — в первом столбце находится номер подмножества, а во втором единичками помечены элементы, которые в это подмножество входят. Нулевым является пустое подмножество.
Алгоритм этого перебора можно записать в рекурсивной форме в виде процедуры, которая принимает на вход частично сформированное множество элементов
и множество оставшихся элементов
:
1) Если множество
не пусто перейти к пункту 4)
2) Выдать в качестве результата множество
3) Закончить процедуру
4) Образовать новое множество
, исключив из множества
первый элемент
5) Вызвать себя рекурсивно, передав в качестве параметров множества
и
6) Образовать новое множество
, добавив в него первый элемент множества
7) Вызвать себя рекурсивно, передав в качестве параметров множества
и
8) Закончить процедуру
Корневой вызов рекурсии производится с пустым множеством
, а множество
содержит исходное множество.
Разумеется, этот алгоритм можно избавить от рекурсии, развернув в единственный цикл, используя для этого единственную индексную переменную и вспомогательный массив, в котором будут храниться флаги того, входит соответствующий элемент множества в получаемое подмножество или нет. Вариант программы реализующий такой развернутый в цикл перебор я нашёл
в конце вот этой странички.
Однако, такой перебор не всегда оптимален. Оптимизируя одну из задач я придумал другой,
особый вариант перебора. В рекуррентной форме он выглядит так (на вход так же принимаются множества
и
, но кроме того — флаг):
1) Если флаг взведён, то выдать в качестве результата множество
2) Образовать новое множество
, добавив в него первый элемент множества
3) Если множество
содержит более одного элемента перейти к пункту 6)
4) Выдать в качестве результата множество
5) Закончить процедуру
6) Образовать новое множество
, исключив из множества
первый элемент
7) Вызвать себя рекурсивно, передав в качестве параметров множества
и
и взведённый флаг
8) Вызвать себя рекурсивно, передав в качестве параметров множества
и
и сброшенный флаг
9) Закончить процедуру
Корневой вызов рекурсии так же производится с пустым множеством
, множеством
, содержащим исходное множество, и взведённым флагом.
Такой перебор породит следующие последовательности подмножеств:
0 0 2 1
1 1 2 0
0 00 00 4 3
1 10 1* 3 1
2 11 1* 3 0
3 01 01 4 0
0 000 000 8 7
1 100 1** 5 3
2 110 1** 4 1
3 111 1** 4 0
4 101 1** 5 0
5 010 01* 7 1
6 011 01* 7 0
7 001 001 8 0(Для четырёх элементов)
_0_0000_0000_16_15
_1_1000_1***__9__7
_2_1100_1***__6__3
_3_1110_1***__5__1
_4_1111_1***__5__0
_5_1101_1***__6__0
_6_1010_1***__8__1
_7_1011_1***__8__0
_8_1001_1***__9__0
_9_0100_01**_13__3
10_0110_01**_12__1
11_0111_01**_12__0
12_0101_01**_13__0
13_0010_001*_15__1
14_0011_001*_15__0
15_0001_0001_16__0
(Для пяти элементов)
_0_00000_00000_32_31
_1_10000_1****_17_15
_2_11000_1****_10__7
_3_11100_1****__7__3
_4_11110_1****__6__1
_5_11111_1****__6__0
_6_11101_1****__7__0
_7_11010_1****__9__1
_8_11011_1****__9__0
_9_11001_1****_10__0
10_10100_1****_14__3
11_10110_1****_13__1
12_10111_1****_13__0
13_10101_1****_14__0
14_10010_1****_16__1
15_10011_1****_16__0
16_10001_1****_17__0
17_01000_01***_25__7
18_01100_01***_22__3
19_01110_01***_21__1
20_01111_01***_21__0
21_01101_01***_22__0
22_01010_01***_24__1
23_01011_01***_24__0
24_01001_01***_25__0
25_00100_001**_29__3
26_00110_001**_28__1
27_00111_001**_28__0
28_00101_001**_29__0
29_00010_0001*_31__1
30_00011_0001*_31__0
31_00001_00001_32__0
Здесь в первом столбце номер подмножества, во втором единичками помечены элементы, входящие в это подмножество, в третьем приведена маска текущего подмножества, отсылающая к варианту с меньшим числом элементов (рекурсия).
Такой способ перебора оптимален в том смысле, что он позволяет оценить характеристику полученного подмножества и, если оно неудовлетворительно, пропустить все неудовлетворительные подмножества, которые порождаются текущим (их количество указано в пятом столбце и равно
, где
— число не рассмотренных на данном шаге элементов исходного множества) и перейти к просмотру следующего потенциально удовлетворительного подмножества (его номер указан в четвёртом столбце). Если быть совсем конкретным, то я решаю задачу, заключающуюся в том, чтобы найти такой набор элементов заданного множества чисел, что их сумма равна заданному числу (разновидность задачи о размене). Хотя аналогичный перебор нужен и в других задачах, например, разбить заданное множество чисел на два так, чтобы суммы получившихся двух множеств отличались минимально. Или задача о ранце, когда надо уложить в рюкзак ограниченного объёма предметы известного объёма, чтобы рюкзак был максимально наполнен.
Мой вопрос заключается в следующем. Помогите, пожалуйста, найти/создать код, который будет развёрнутым в цикл вариантом приведённой рекурсии, аналогично самому первому алгоритму. Сгодится ссылка на какую-нибудь статью или обсуждение этого вопроса. Поскольку задача частая, то наверняка её кто-нибудь да решал. Просто советам о том, как подойти к задаче тоже буду очень благодарен.
Заранее спасибо за любую помощь.