He estado tratando de encontrar una manera de generar todas las particiones distintas de tamaño n de un conjunto múltiple, pero hasta ahora he aparecido con las manos vacías. Primero déjame mostrarte lo que estoy tratando de archivar.

Digamos que tenemos un vector de entrada deuint32_t:

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

Y digamos que queremos crear todas las particiones distintas de 2 tamaños. Solo hay dos de estos, a saber:

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

Tenga en cuenta que el orden no importa, es decir, todas las siguientes son soluciones duplicadas e incorrectas.

Duplicar porque el orden dentro de un grupo de permutación no importa:

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

Duplicar porque el orden de los grupos no importa:

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

No es tarea de algún tipo, por cierto. Encontré esto mientras codificaba algo en el trabajo, pero ahora es por interés personal que me gustaría saber cómo lidiar con esto. Los parámetros para el problema relacionado con el trabajo eran lo suficientemente pequeños como para que generar un par de miles de soluciones duplicadas realmente no importara.

Solución actual (genera duplicados)

Para ilustrar que no solo estoy preguntando sin haber intentado encontrar una solución, permítanme tratar de explicar mi algoritmo actual (que genera soluciones duplicadas cuando se usa con multisets).

Funciona de la siguiente manera: el estado tiene un conjunto de bits con n bits establecidos en 1 para cada bloque de partición. La longitud de los conjuntos de bits essize(input) - n * index_block(), p.ej. si el vector de entrada tiene 8 elementos yn = 2, entonces el primer bloque de partición usa un conjunto de bits de 8 bits con 2 bits establecido en 1, el siguiente bloque de partición usa un conjunto de bits de 6 bits con 2 bits establecido en 1, etc.

Se crea una partición a partir de estos conjuntos de bits iterando sobre cada conjunto de bits en orden y extrayendo los elementos del vector de entrada con índices iguales a la posición de 1 bits en el conjunto de bits actual.

Para generar la siguiente partición, itero sobre los conjuntos de bits en orden inverso. Se calcula la siguiente permutación de bitset (usando un reverso del truco de Gosper). Si el primer bit en el conjunto de bits actual no está establecido (es decir, el índice de vector 0 no está seleccionado), entonces ese conjunto de bits se restablece a su estado inicial. Hacer cumplir que el primer bit siempre esté establecido evita generar duplicados al crear particiones de conjunto tamaño-n (duplicados del segundo tipo que se muestra arriba). Si el conjunto de bits actual es igual a su valor inicial, este paso se repite para el conjunto de bits anterior (más largo).

Esto funciona muy bien (y muy rápido) para conjuntos. Sin embargo, cuando se usa con varios conjuntos genera soluciones duplicadas, ya que no es consciente de que ambos elementos aparecen más de una vez en el vector de entrada. Aquí hay un ejemplo de salida:

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]]

Esa última solución (duplicada) se genera simplemente porque el algoritmo no es consciente de los duplicados en la entrada, genera exactamente los mismos estados internos (es decir, qué índices seleccionar) en ambos ejemplos.

Solución deseada

Supongo que ahora es bastante claro con lo que estoy tratando de terminar. Solo en aras de la exhaustividad, se vería algo así:

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]]

Es decir. el código funcionaría algo así comostd::next_permutation, informando que ha generado todas las soluciones y ha terminado de nuevo en la "primera" solución (para cualquier definición de primero que desee utilizar, probablemente lexicográficamente, pero no es necesario que lo sea).

El algoritmo relacionado más cercano que encontré es el Algoritmo M de The Art of Computer Programming de Knuth, Volumen 4 Parte 1, sección 7.2.1.5 (p. 430). Sin embargo, eso genera todas las particiones multiset posibles. También hay un ejercicio en el libro (7.2.1.5.69, solución en la p. 778) sobre cómo modificar Alg. M para generar solo soluciones con como máximo r particiones. Sin embargo, eso todavía permite particiones de diferentes tamaños (p. Ej.[[1, 2, 2], [1]] sería una salida válida para r = 2).

¿Alguna idea / truco / algoritmo existente sobre cómo hacer esto? Tenga en cuenta que la solución debe ser eficiente, es decir, hacer un seguimiento de todas las soluciones generadas previamente, averiguar si la que se genera actualmente es una permutación y, de ser así, omitirla, no es factible debido a la velocidad con la que el espacio de la solución explota para entradas más largas con más duplicados