Я пытался найти способ генерирования всех отдельных разделов размера 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).

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