Особый алгоритм перебора всех подмножеств мультимножества

[B@R5uk]

В различных задачах оптимизации частенько приходится перебирать все возможные варианты, в частности все возможные подмножества заданного множества. В этой задаче всего $2^N$ комбинаций, где $N$ — мощность множества. Простейший алгоритм перебора тесно связан с двоичным разложением номера перебираемой комбинации. Например:
__123
0_000
1_100
2_010
3_110
4_001
5_101
6_011
7_111
Здесь в первой строке записаны номера элементов множества (которое состоит из трёх элементов), в следующих строках — в первом столбце находится номер подмножества, а во втором единичками помечены элементы, которые в это подмножество входят. Нулевым является пустое подмножество.

Алгоритм этого перебора можно записать в рекурсивной форме в виде процедуры, которая принимает на вход частично сформированное множество элементов $A$ и множество оставшихся элементов $B$:
1) Если множество $B$ не пусто перейти к пункту 4)
2) Выдать в качестве результата множество $A$
3) Закончить процедуру
4) Образовать новое множество $B'$, исключив из множества $B$ первый элемент
5) Вызвать себя рекурсивно, передав в качестве параметров множества $A$ и $B'$
6) Образовать новое множество $A'$, добавив в него первый элемент множества $B$
7) Вызвать себя рекурсивно, передав в качестве параметров множества $A'$ и $B'$
8) Закончить процедуру
Корневой вызов рекурсии производится с пустым множеством $A$, а множество $B$ содержит исходное множество.

Разумеется, этот алгоритм можно избавить от рекурсии, развернув в единственный цикл, используя для этого единственную индексную переменную и вспомогательный массив, в котором будут храниться флаги того, входит соответствующий элемент множества в получаемое подмножество или нет. Вариант программы реализующий такой развернутый в цикл перебор я нашёл в конце вот этой странички.

Однако, такой перебор не всегда оптимален. Оптимизируя одну из задач я придумал другой, особый вариант перебора. В рекуррентной форме он выглядит так (на вход так же принимаются множества $A$ и $B$, но кроме того — флаг):
1) Если флаг взведён, то выдать в качестве результата множество $A$
2) Образовать новое множество $A'$, добавив в него первый элемент множества $B$
3) Если множество $B$ содержит более одного элемента перейти к пункту 6)
4) Выдать в качестве результата множество $A'$
5) Закончить процедуру
6) Образовать новое множество $B'$, исключив из множества $B$ первый элемент
7) Вызвать себя рекурсивно, передав в качестве параметров множества $A'$ и $B'$ и взведённый флаг
8) Вызвать себя рекурсивно, передав в качестве параметров множества $A$ и $B'$ и сброшенный флаг
9) Закончить процедуру
Корневой вызов рекурсии так же производится с пустым множеством $A$, множеством $B$, содержащим исходное множество, и взведённым флагом.

Такой перебор породит следующие последовательности подмножеств:
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

Здесь в первом столбце номер подмножества, во втором единичками помечены элементы, входящие в это подмножество, в третьем приведена маска текущего подмножества, отсылающая к варианту с меньшим числом элементов (рекурсия).

Такой способ перебора оптимален в том смысле, что он позволяет оценить характеристику полученного подмножества и, если оно неудовлетворительно, пропустить все неудовлетворительные подмножества, которые порождаются текущим (их количество указано в пятом столбце и равно $2^M-1$, где $M$ — число не рассмотренных на данном шаге элементов исходного множества) и перейти к просмотру следующего потенциально удовлетворительного подмножества (его номер указан в четвёртом столбце). Если быть совсем конкретным, то я решаю задачу, заключающуюся в том, чтобы найти такой набор элементов заданного множества чисел, что их сумма равна заданному числу (разновидность задачи о размене). Хотя аналогичный перебор нужен и в других задачах, например, разбить заданное множество чисел на два так, чтобы суммы получившихся двух множеств отличались минимально. Или задача о ранце, когда надо уложить в рюкзак ограниченного объёма предметы известного объёма, чтобы рюкзак был максимально наполнен.

Мой вопрос заключается в следующем. Помогите, пожалуйста, найти/создать код, который будет развёрнутым в цикл вариантом приведённой рекурсии, аналогично самому первому алгоритму. Сгодится ссылка на какую-нибудь статью или обсуждение этого вопроса. Поскольку задача частая, то наверняка её кто-нибудь да решал. Просто советам о том, как подойти к задаче тоже буду очень благодарен.

Заранее спасибо за любую помощь.

[arseniiv]

Любую рекурсию можно развернуть с помощью использования стека, примерно как это делается на самом низком уровне со стеком вызовов. В вашем случае всё ещё лучше, потому что все рекурсивные вызовы идут толпой сразу перед возвратом. Тогда мы можем использовать схему, которую можно назвать «схемой заданий» (вообще у этого должно быть, наверно, имя поиск в глубину, но не помню). Если есть функция, которая вызывает себя в конце $n$ раз с наборами параметров $A_1,\ldots,A_n$, то вызов такой функции с набором параметров $A$ можно преобразовать в такой код со стеком:

0. Имеем стек, содержащий только $A$.
В цикле, пока стек непустой:
1. Подбираем из стека набор параметров.
2. Выполняем с ним кусок функции до рекурсивных вызовов без всяких изменений.
3. Вместо рекурсивных вызовов запихиваем в стек $A_n,\ldots,A_1$ (в обратном порядке, потому что выходить-то они будут тоже в обратном).

После этого можно ещё заняться оптимизациями, наверно.

[mustitz]

Биномиальные деревья, Д. Кнут, том 4А, страница 413. Они?

[B@R5uk]

arseniiv, спасибо, идея интересная. Но хотелось бы обойтись одним-двумя массивами, которые будут на каждом шаге модифицироваться, потому что хранить в стеке все параметры будет очень накладно. В качестве иллюстрации вот код на Java, реализующий перебор для самого первого случая:

Используется синтаксис Java

public class StudySubsetSearch2 {
        
        private static final int size = 4;
        
        public static void main(String[] args) {
                int[] array = new int[size];
                int index = 0;
                while (true) {
                        display(array);
                        while (size > index && 1 == array[index]) {
                                array[index] = 0;
                                ++index;
                        }
                        if (size == index) {
                                break;
                        }
                        array[index] = 1;
                        index = 0;
                }
        }
        
        private static void display(int[] array) {
                int n, size;
                size = array.length;
                for (n = 0; size > n; ++n) {
                        System.out.print(array[n]);
                }
                System.out.println();
        }
}

Вот эта часть кода:

Используется синтаксис Java

                        while (size > index && 1 == array[index]) {
                                array[index] = 0;
                                ++index;
                        }
                        if (size == index) {
                                break;
                        }
                        array[index] = 1;
                        index = 0;

реализует переход от одного множества к другому, а так же проверяет окончание перебора. Именно это я бы и хотел.

mustitz в сообщении #1286899 писал(а):

Биномиальные деревья

Не совсем понимаю (вернее даже совсем не понимаю): как деревья можно связать со множествами?

[Dmitriy40]

B@R5uk в сообщении #1286924 писал(а):

как деревья можно связать со множествами?

Совокупность всех листьев дерева - множество. Перечисление узлов на пути от вершины к листу - запись элемента множества, в частном случае двоичная.

[B@R5uk]

Dmitriy40 в сообщении #1286925 писал(а):

Перечисление узлов на пути от вершины к листу - запись элемента множества, в частном случае двоичная.

Если честно, совсем не понимаю. Можно какой-нибудь наглядных пример с тремя-четырьмя элементами?

[Dmitriy40]

B@R5uk в сообщении #1286926 писал(а):

Можно какой-нибудь наглядных пример с тремя-четырьмя элементами?

Ок, вот пример биноминального дерева с 4-мя листьями:

Используется синтаксис Text

Цифрами обозначены рёбра (дуги, ветви, как там их ещё называют).
                        вершина
          0                               1
        узел                            узел
  0               1               0               1
лист0           лист1           лист2           лист3

Есть всего 4 пути из вершины до листьев:
00 - лист 0
01 - лист 1
10 - лист 2
11 - лист 3
Как хорошо видно двоичная запись номера листа и является путём из вершины по рёбрам в данный лист. В Ваших обозначениях двоичная запись перевёрнута и вершина находится справа от числа, а не слева, что кстати неудобно.

[B@R5uk]

Dmitriy40, спасибо. Но тогда расход памяти для перебора элементов множества будет экспоненциальным относительно размера множества. Или перебор можно реализовать не стоя дерево целиком?

Плюс биномиальное дерево имеет различную высоту в различных направлениях, поэтому не совсем понятно, как каждому листу сопоставить подмножество.

[Dmitriy40]

Так, кажется я ошибся с названием и это не именно биноминальное дерево, в том в узлах тоже сидят значения, у меня же значения лишь в листьях. Перебор моего варианта вообще памяти не требует, лишь на счётчик в $N=\log_2 n$ битов и всё.
В двоичной куче (или сортирующем дереве, это частный случай биноминального дерева) все нужные Вам операции выполняются или за $O(n)$ (построение дерева), или за $O(\log n)$ (выборка из него минимального/максимального элемента). Потому перебор сводится к $n$ раз удалению максимального элемента и требует общего времени $O(n \log n)$, что вовсе не экспоненциально.
Построив дерево правильно (смотря что именно хранить в узлах дерева) Вы сможете не обходить его всё, а отсекать нижние ветки при достижении заданного условия, что уж точно не медленнее $O(n \log n)$.
$n$ - количество элементов множества, часто $n=2^N$.
И для хранения дерева дополнительной памяти вообще не требуется, оно хранится в той же памяти что и массив элементов множества, их лишь по хитрому переставляют.
Короче, деревья - вещь! Надо лишь уметь их правильно готовить строить.

[arseniiv]

B@R5uk в сообщении #1286924 писал(а):

Но хотелось бы обойтись одним-двумя массивами, которые будут на каждом шаге модифицироваться, потому что хранить в стеке все параметры будет очень накладно.

Насколько я понял (не особо вник), одно из множеств (почти) представляется левой частью двоичной записи, а другое (почти) представляется правой, и флаг тоже оттуда можно достать. Если так, хранить в стеке будет нужно лишь пару индексов.

Но лучше и правда подумать о дереве: действительно ведь, отсечение происходит раньше генерации множества, надмножества которого мы хотим отсекать, так что незачем перечислять подмножества в странном порядке. Для обхода этого дерева предварительно генерировать его и впрямь не нужно. В стек отправятся верхние по отношению к текущему положению узлы; если в универсальном множестве элементов не больше, чем разрядность самого большого целого типа, можно вместо стека использовать число и индекс бита в нём, отсекающего префикс (если элементов менее чем в десятки раз больше, массив чисел и индекс; ну а если разнообразие элементов ещё хлеще, то придётся химичить).

Dmitriy40
Так тут в биномиальном дереве будут храниться подмножества, а не элементы, так что место экспоненциальное от числа элементов. Но зачем хранить подмножества и дерево, я так и не понял — нам нужен только обход (в глубину), для этого нужно памяти максимум как число элементов (чтобы держать в уме неизменяемую часть подмножеств).

[Dmitriy40]

arseniiv
Я не вникал в метод перебора, влез лишь для демонстрации возможного сопряжения деревьев и множеств.
Но на беглый взгляд кажется что сформировав дерево правильно (с некоей функцией значений в поддеревьях в каждом узле, типа суммы всех элементов поддеревьев) можно обходить дерево по ветвям с вершины с отсечением поддеревьев по некоему условию. При этом дерево будет оставаться сбалансированным двоичным, высота его для всех ветвей отличаться лишь на 1, перебор линеен относительно количества элементов, дополнительной памяти надо не более $n$ (для узлов дерева, причём хранится число, а не множества). Но это смутная догадка, повторю, в метод не вникал.

[arseniiv]

Ну вообще конкретно для суммы можно много придумать, видимо. Кластеризовать элементы в какое-то дерево по их суммам, чтобы побольше отбрасывать перелётов, или по дополнениям сумм до полной, чтобы отбрасывать недолёты (а вот как совместить то и это, не представляю).

[B@R5uk]

Вот, я таки придумал код, который выдаёт последовательность ноликов и единичек, которая мне нужна:

Используется синтаксис Java

public class StudySubsetSearch4 {
        
        private static final int size = 5;
        
        public static void main(String[] args) {
                int[] array = new int[size];
                int index = 0;
                boolean isFlagged;
                while (true) {
                        display(array);
                        index = 0;
                        isFlagged = 1 == array[0];
                        if (isFlagged) {
                                array[0] = 0;
                                ++index;
                        }
                        while (size > index && 0 == array[index]) {
                                ++index;
                        }
                        if (isFlagged) {
                                if (size == index) {
                                        break;
                                }
                                array[index] = 0;
                        }
                        --index;
                        array[index] = 1;
                }
        }
        
        private static void display(int[] array) {
                int n, size;
                size = array.length;
                for (n = 0; size > n; ++n) {
                        System.out.print(array[n]);
                }
                System.out.println();
        }
}
 

Однако, мне теперь не нравится, что массив просматривается с конца. Лучше бы это было с начала, хотя и будет получаться зеркально отражённые значения. Переделал. Теперь надо понять, как правильно этот код преобразовать в работу с суммами, чтобы это было наиболее эффективно и каждая сумма не считалась с самого начала.

[mustitz]

B@R5uk в сообщении #1286924 писал(а):

mustitz в сообщении #1286899 писал(а):

Биномиальные деревья

Не совсем понимаю (вернее даже совсем не понимаю): как деревья можно связать со множествами?

Вот пример дерева (стр. 413)


У этого дерева ровно $2^n$ узлов, каждый из которых соответствует некоторому подмножества множества из $n$ элементов. Каждое ребро это добавление элемента во множество. Если решать задачу о рюкзаке, то при обхоже дерева если рюкзак переполняется, то нам нет смысла спускаться по листьям ниже, это привёдёт только к добавлению новых вещей в уже переполенный рюкзак.

-- 24.01.2018, 18:41 --

Собственно говоря, алгоритм заполнения рюкзака из Д. Кнута (стр. 414)

[B@R5uk]

B@R5uk в сообщении #1287123 писал(а):

Теперь надо понять, как правильно этот код преобразовать в работу с суммами, чтобы это было наиболее эффективно и каждая сумма не считалась с самого начала.

Оказывается, ничего перерабатывать не надо. В отличие от обычного двоичного перебора, где для эффективности нужно хранить все промежуточные суммы, полученные перед данной последовательным прибавлением элементов, в моём алгоритме перебора этого не требуется. У меня на каждом шаге либо добавляется один элемент, либо удаляются два и добавляется один. То есть можно работать только с одной суммой, и вне зависимости от размера исходного множества операция расчёта нужной суммы при переходе к следующей комбинации элементов выполняется за константное время.

То есть, всё, что нужно сделать, — это заменить строки
array[index] = 0; и
array[index] = 1; на группу строк
array[index] = 0;
sum -= values[index]; и
array[index] = 1;
sum += values[index];

Однако, в приведённом мной выше алгоритме мне очень не нравится наличие вложенного цикла, в котором ищется следующий не нулевой флаг в массиве флагов добавленных элементов множества. Так же каждую четвёртую перебираемую комбинацию самый последний элемент сначала вычитается из суммы, а потом он же к ней и прибавляется. Первую проблему я решил добавлением списка индексов, указывающих на следующий уже добавленный элемент, а вторую — внедрением конечного автомата на четыре состояния, соответствующим наличию/отсутствию перебираемом подмножестве первых двух элементов исходного множества. Это ограничит алгоритм возможностью перебирать только множества, в которых есть хотя бы два элемента, но это не самая страшная потеря: множества из одного элемента или вообще пустые интереса не представляют.

Вот такой получился на данном этапе код:

Используется синтаксис Java

public class StudySubsetSearch5 {
        
        private static final int size = 7;
        
        public static void main(String[] args) {
                int[] array = new int[size];
                int[] indices = new int[size];
                int state, index, lastIndex;
                boolean isActive = true;
                state = 0;
                index = size;
                while (isActive) {
                        display(array);
                        switch (state) {
                        case 0:
                                lastIndex = index;
                                --index;
                                indices[index] = lastIndex;
                                array[index] = 1;
                                if (1 == index) {
                                        state = 1;
                                }
                                break;
                        case 1:
                                array[0] = 1;
                                state = 2;
                                break;
                        case 2:
                                array[1] = 0;
                                state = 3;
                                break;
                        default:
                                array[0] = 0;
                                index = indices[1];
                                if (size == index) {
                                        isActive = false;
                                        break;
                                }
                                lastIndex = indices[index];
                                array[index] = 0;
                                --index;
                                indices[index] = lastIndex;
                                array[index] = 1;
                                if (1 == index) {
                                        state = 1;
                                } else {
                                        state = 0;
                                }
                                break;
                        }
                }
        }
        
        private static void display(int[] array) {
                int n, size;
                size = array.length;
                for (n = 0; size > n; ++n) {
                        System.out.print(array[n]);
                }
                System.out.println();
        }
}
 

Осталось понять, как пропускать группы неудачных комбинаций.

-- 25.01.2018, 15:00 --

mustitz, спасибо за ссылку на хорошую книгу и за цитаты. Я просмотрел по диагонали то, что пишет автор. Он действительно решает ту же задачу, и, вроде бы, даже способом похожим на мой. Но он не привёл никакого кода, который можно было бы набрать и подвергнуть трассировке, а я не смог вникнуть, что же именно он там делает. Думаю, что книга требует неспешного изучения с самого начала: с принятых обозначений и договорённостей. Поскольку это требует времени (а читаю я не очень), то я хочу в первую очередь добить свой алгоритм. Не хорошо бросать на пол пути начатое дело. Тем более, результат вроде уже виднеется на горизонте. Если есть рекомендации по моему коду, буду очень рад их услышать.