Алгоритм генерации всех мультимножественных разделов размера n

Я пытался найти способ генерирования всех отдельных разделов размера n в мультимножестве, но до сих пор подходил с пустыми руками. Сначала позвольте мне показать, что я пытаюсь архивировать.

Допустим, у нас есть входной векторuint32_t:

std::vector<uint32_t> input = {1, 1, 2, 2}

Допустим, мы хотим создать все отдельные 2-размерные разделы. Есть только два из них, а именно:

[[1, 1], [2, 2]], [[1, 2], [1, 2]]

Обратите внимание, что порядок не имеет значения, т. Е. Все нижеприведенное является неправильным решением.

Дублируйте, потому что порядок в группе перестановок не имеет значения:

[[2, 1], [1, 2]]

Дублируйте, потому что порядок групп не имеет значения:

[[2, 2], [1, 1]]

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

Текущее решение (генерирует дубликаты)

Чтобы проиллюстрировать, что я не просто спрашиваю, не пытаясь найти решение, позвольте мне попытаться объяснить мой текущий алгоритм (который генерирует повторяющиеся решения при использовании с мультимножествами).

Это работает следующим образом: состояние имеет битовый набор с n битами, установленными в 1 для каждого блока разбиения. Длина набора битовsize(input) - n * index_block()например, если входной вектор имеет 8 элементов и n = 2, то первый блок разбиения использует 8-битный набор битов с 2 битами, установленными в 1, следующий блок разбиения использует 6-битный набор битов с 2 битами, установленными в 1, и т. д.

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

Чтобы создать следующий раздел, я перебираю наборы битов в обратном порядке. Следующая битовая перестановка вычисляется (с использованием обратного взлома Госпера). Если первый бит в текущем наборе битов не установлен (т.е. векторный индекс 0 не выбран), то этот набор битов сбрасывается в исходное состояние. Обеспечение того, чтобы первый бит был всегда установлен, предотвращает создание дубликатов при создании разделов с заданным размером n (дубликаты второго типа показаны выше). Если текущий набор битов равен его начальному значению, этот шаг затем повторяется для предыдущего (более длинного) набора битов.

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

std::vector<uint32_t> input = {1, 2, 3, 4};
printAllSolutions(myCurrentAlgo(input, 2));
=> [[2, 1], [4, 3]], [[3, 1], [4, 2]], [[4, 1], [3, 2]]

std::vector<uint32_t> input = {1, 1, 2, 2};
printAllSolutions(myCurrentAlgo(input, 2));
=> [[1, 1], [2, 2]], [[2, 1], [2, 1]], [[2, 1], [2, 1]]

Последнее (дублированное) решение генерируется просто потому, что алгоритм не знает дубликатов на входе, он генерирует одинаковые внутренние состояния (то есть, какие индексы выбирать) в обоих примерах.

Требуется решение

Я предполагаю, что к настоящему времени ясно, что я пытаюсь закончить. Для полноты картины это будет выглядеть следующим образом:

std::vector<uint32_t> multiset = {1, 1, 2, 2};
MagicClass myGenerator(multiset, 2);
do {
  std::vector<std::vector<uint32_t> > nextSolution = myGenerator.getCurrent();
  std::cout << nextSolution << std::endl;
} while (myGenerator.calcNext());
=> [[1, 1], [2, 2]]
   [[1, 2], [1, 2]]

То есть код будет работать примерно такstd::next_permutation, сообщая, что он породил все решения и вернулся к «первому» решению (для любого определения первого, которое вы хотите использовать, вероятно, лексикографически, но не обязательно).

Самый близкий связанный алгоритм, который я нашел, - это Алгоритм М из книги Кнута «Искусство компьютерного программирования», том 4, часть 1, раздел 7.2.1.5 (с. 430). Тем не менее, это создает все возможные многосетевые разделы. В книге также приведено упражнение (7.2.1.5.69, решение на стр. 778) о том, как изменить Alg. M, чтобы генерировать только решения с не более чем r разделами. Тем не менее, это по-прежнему позволяет разделы разных размеров (например,[[1, 2, 2], [1]] будет правильным выходом для г = 2).

Любые идеи / хитрости / существующие алгоритмы о том, как это сделать? Обратите внимание, что решение должно быть эффективным, то есть отслеживать все ранее созданные решения, выяснить, является ли созданное в настоящее время перестановкой и, если это так, пропустить его, невозможно из-за скорости, с которой пространство решения взрывается для более длинных входов с большим количеством дубликаты.

 Jacob27 мая 2016 г., 16:11
Вы можете просто удалить дубликаты на входе?
 Darhuuk27 мая 2016 г., 18:24
Конечно, создайте любое требуемое состояние (желательно линейное по размеру входных данных).
 Darhuuk30 мая 2016 г., 23:33
Я считаю, что нашел эффективное решение. Я, вероятно, успею реализовать и протестировать его позже на этой неделе. Оставайтесь в курсе :).

Ответы на вопрос(1)

основан на нескольких простых правилах:

Начните с сортировки или подсчета различных элементов; они не должны быть в каком-то определенном порядке, вы просто хотите сгруппировать идентичные элементы вместе.(Этот шаг упростит некоторые из следующих шагов, но может быть пропущен.)
   {A,B,D,C,C,D,B,A,C} -> {A,A,B,B,D,D,C,C,C}  
Начните с пустого решения и вставьте элементы один за другим, используя следующие правила:
   { , , } { , , } { , , }  
Перед вставкой элемента найдите дублирующие блоки, например:
   {A, , } { , , } { , , }  
                    ^dup^

   {A, , } {A, , } {A, , }  
            ^dup^   ^dup^
Вставьте элемент в каждый неповторяющийся блок с доступным пространством:
   partial solution: {A, , } {A, , } { , , }  
                              ^dup^

   insert element B: {A,B, } {A, , } { , , }  
                     {A, , } {A, , } {B, , }  
Если идентичный элемент уже присутствует, не помещайте новый элемент перед ним:
   partial solution:  {A, , } {B, , } { , , }  
   insert another B:  {A,B, } {B, , } { , , }  <- ILLEGAL  
                      {A, , } {B,B, } { , , }  <- OK
                      {A, , } {B, , } {B, , }  <- OK
При вставке элемента, в котором есть еще N идентичных элементов, не забудьте оставить N открытых мест после текущего элемента:
   partial solution:  {A, , } {A, , } {B,B, }  
   insert first D:    {A,D, } {A, , } {B,B, }  <- OK  
                      {A, , } {A, , } {B,B,D}  <- ILLEGAL (NO SPACE FOR 2ND D)  
Последняя группа идентичных элементов может быть вставлена ​​за один раз:
   partial solution:  {A,A, } {B,B,D} {D, , }  
   insert C,C,C:      {A,A,C} {B,B,D} {D,C,C}  

Таким образом, алгоритм будет выглядеть примерно так:

// PREPARATION  
Sort or group input.              // {A,B,D,C,C,D,B,A,C} -> {A,A,B,B,D,D,C,C,C}  
Create empty partial solution.    // { , , } { , , } { , , }  
Start recursion with empty partial solution and index at start of input.  

// RECURSION  
Receive partial solution, index, group size and last-used block.  
If group size is zero:  
    Find group size of identical elements in input, starting at index.  
    Set last-used block to first block.  
Find empty places in partial solution, starting at last-used block.  
If index is at last group in input:  
    Fill empty spaces with elements of last group.
    Store complete solution.
    Return from recursion.
Mark duplicate blocks in partial solution.  
For each block in partial solution, starting at last-used block:  
    If current block is not a duplicate, and has empty places,  
    and the places left in current and later blocks is not less than the group size:
        Insert element into copy of partial solution.
        Recurse with copy, index + 1, group size - 1, current block.

Я протестировал простую реализацию этого алгоритма на JavaScript, и он дает правильный результат.

 Darhuuk02 июн. 2016 г., 18:23
@ גלעדברקן Алгоритм псевдокода m69 генерирует все возможные решения, а затем удаляет дубликаты, что становится невероятно медленным (подумайте о столетиях вычислений) и требует практически неограниченного хранения даже для умеренных входных наборов. Алгоритм, который я опубликовал, генерирует следующее решение (так что для нескольких временных переменных требуется только O (1) хранилище) и никогда не генерирует дубликаты.
 m6902 июн. 2016 г., 20:11
@Darhuuk Новая версия больше не генерирует дубликаты, но, вероятно, все еще медленнее, чем ваш код. (Передача последней использованной блочной переменной позволяет избежать дубликатов.)
 m6903 июн. 2016 г., 02:55
@ גלעדברקן Количество решений быстро становится огромным; Распределение 20 номеров на 4 блока по 5 уже дало мне в среднем 9 380 382 решения, для которых требовалось 19 867 495 рекурсий. Конечно, глубина рекурсии и количество частичных решений, хранящихся в памяти, в этом случае никогда не превышают 20. Но версия js занимает больше 10 секунд, поэтому даже на серьезном языке это никогда не будет достаточно быстрым для больших массивов.
 גלעד ברקן02 июн. 2016 г., 05:44
Большой! Обычно это приятное чувство, чтобы понять вещи. Я думаю, что я потерял ход мыслей по этому вопросу, хотя.
 גלעד ברקן02 июн. 2016 г., 13:49
Как его решение лучше (я не читал это)?
 m6902 июн. 2016 г., 05:16
@ גלעדברקן Я протестировал версию нового алгоритма без разделов, и, похоже, он работает правильно.
 m6929 мая 2016 г., 18:20
@Darhuuk Я вижу способ, например, где {A ,,} {B, B,} {B, B,} {,,} имеет сопровождающий массив типа [0,1,1,0], который указывает, находится ли каждая часть в группе дубликатов, или сколько дубликаты у него есть, но это потребует дополнительного пространства и расчетов. Я все еще надеюсь, что мы сможем найти более элегантное решение.
 גלעד ברקן03 июн. 2016 г., 03:49
Ну, я не спешу. Кто сказал, что компьютеры должны вернуться быстро.
 m6902 июн. 2016 г., 05:55
@ גלעדברקן Как только я задремал от вопроса, даже самое лучшее решение от автора не остановит меня! :-)
 Darhuuk29 мая 2016 г., 09:22
Хорошая идея с перегородками. Проблема с обнаружением дубликата состоит в том, что он должен быть сгенерирован первым. Для больших входов с большим количеством повторяющихся записей это быстро становится невозможным, потому что количество дубликатов намного больше, чем общее количество решений.
 גלעד ברקן29 мая 2016 г., 19:37
Что касается самого последнего блока наборов в вашем ответе, вы должны быть в состоянии избежать дублированияbb0 000 с000 bb0 распределяя только в нисходящих частях внутри блоков с одинаковым количеством.

Ваш ответ на вопрос