Eu tenho tentado descobrir uma maneira de gerar todas as partições distintas de tamanho n de um multiset, mas até agora surgiram de mãos vazias. Primeiro, deixe-me mostrar o que estou tentando arquivar.

Digamos que temos um vetor de entrada deuint32_t:

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

Digamos que queremos criar todas as partições distintas de dois tamanhos. Existem apenas dois deles, a saber:

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

Observe que o pedido não importa, ou seja, todos os itens a seguir são soluções duplicadas e incorretas.

Duplicar porque a ordem dentro de um grupo de permutação não importa:

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

Duplicar porque a ordem dos grupos não importa:

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

Não é dever de casa de algum tipo. Encontrei isso ao codificar algo no trabalho, mas agora é de interesse pessoal que eu gostaria de saber como lidar com isso. Os parâmetros para o problema relacionado ao trabalho eram pequenos o suficiente para que gerar milhares de soluções duplicadas não importasse.

Solução atual (gera duplicatas)

Para ilustrar que não estou apenas perguntando sem ter tentado encontrar uma solução, deixe-me tentar explicar meu algoritmo atual (que gera soluções duplicadas quando usado com vários conjuntos).

Funciona da seguinte forma: o estado possui um conjunto de bits com n bits definidos como 1 para cada bloco de partição. O comprimento dos bitsets ésize(input) - n * index_block(), por exemplo. se o vetor de entrada tiver 8 elementos en = 2, o primeiro bloco de partição usará um conjunto de bits de 8 bits com 2 bits definido como 1, o próximo bloco de partição usará um conjunto de bits de 6 bits com 2 bits definido como 1, etc.

Uma partição é criada a partir desses bits, iterando cada bit em ordem e extraindo os elementos do vetor de entrada com índices iguais à posição de 1 bits no bit atual.

Para gerar a próxima partição, eu itero sobre os bits na ordem inversa. A próxima permutação de bits é calculada (usando um reverso do hack de Gosper). Se o primeiro bit no conjunto de bits atual não estiver definido (ou seja, o índice de vetor 0 não selecionado), esse conjunto de bits será redefinido para seu estado inicial. A imposição de que o primeiro bit seja sempre definido impede a geração de duplicatas ao criar partições de tamanho n definido (duplicatas do segundo tipo mostradas acima). Se o conjunto de bits atual for igual ao seu valor inicial, essa etapa será repetida para o conjunto de bits anterior (mais longo).

Isso funciona muito bem (e muito rápido) para os sets. No entanto, quando usado com várias configurações, gera soluções duplicadas, pois não se sabe que os dois elementos aparecem mais de uma vez no vetor de entrada. Aqui está um exemplo de saída:

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

Essa última solução (duplicada) é gerada simplesmente porque o algoritmo não tem conhecimento de duplicatas na entrada, gera exatamente os mesmos estados internos (ou seja, quais índices selecionar) nos dois exemplos.

Solução desejada

Acho que agora está bem claro o que estou tentando terminar. Apenas por uma questão de integridade, seria algo como a seguir:

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

I.e. o código funcionaria um pouco comostd::next_permutation, informar que gerou todas as soluções e retornou à "primeira" solução (para qualquer definição de primeira que você deseja usar, provavelmente lexicograficamente, mas não precisa ser).

O algoritmo relacionado mais próximo que encontrei é o Algoritmo M, de Knuth, The Art of Computer Programming, Volume 4 Parte 1, seção 7.2.1.5 (p. 430). No entanto, isso gera todas as partições multiset possíveis. Há também um exercício no livro (7.2.1.5.69, solução na p. 778) sobre como modificar Alg. M para gerar apenas soluções com no máximo r partições. No entanto, isso ainda permite partições de tamanhos diferentes (por exemplo,[[1, 2, 2], [1]] seria uma saída válida para r = 2).

Alguma idéia / truques / algoritmos existentes sobre como fazer isso? Observe que a solução deve ser eficiente, ou seja, acompanhar todas as soluções geradas anteriormente, descobrir se a atualmente gerada é uma permutação e, se for o caso, ignorá-la, é inviável por causa da taxa pela qual o espaço da solução explode para entradas mais longas com mais duplicatas.