假设我们有一个输入向量，其中包含uint32_t类型的元素：
std::vector<uint32_t> input = {1, 1, 2, 2}
假设我们想创建所有不同的2个大小的分区。只有两个这样的分区，即：
[[1, 1], [2, 2]], [[1, 2], [1, 2]]
请注意顺序并不重要，也就是说以下所有的解决方案都是重复且不正确的。
Duplicate because order within a permutation group does not matter:
[[2, 1], [1, 2]]Duplicate because order of groups does not matter:
[[2, 2], [1, 1]]
顺便说一句，这不是某种作业。我在工作中编写代码时遇到了这个问题，但现在只是出于个人兴趣，我想知道如何处理这个问题。与工作相关的问题的参数足够小，以至于生成几千个重复的解决方案并没有真正关系。
当前解决方案（生成重复项）
为了说明我不是没有尝试过提出解决方案而发问，让我尝试解释一下我的当前算法（当与multisets一起使用时会生成重复的解决方案）。
它的工作原理如下：状态具有一个位集，对于每个分区块都设置了n位为1。位集的长度为size(input) - n * index_block()，例如，如果输入向量有8个元素而n = 2，则第一个分区块使用一个8位位集，并且其中有2个位设置为1，下一个分区块使用一个6位位集，并且其中有2个位设置为1等等。
通过按顺序迭代每个位集并提取与当前位集中的1位位置相等的输入向量的元素来从这些位集创建分区。
为了生成下一个分区，我倒序迭代位集。计算下一个位集排列（使用Gosper的反向方法）。如果当前位集中第一个位没有设置（即未选择向量索引0），则该位集将被重置为其起始状态。强制要求第一个位始终设置可以在创建大小n的集合分区时防止生成重复项（如上面显示的第二类重复项）。如果当前位集等于其起始值，则针对以前（更长）的位集重复执行此步骤。
这对于集合非常有效（并且非常快速）。但是，当与multisets一起使用时，它会生成重复解决方案，因为它不知道两个元素在输入向量中出现多次。以下是一些示例输出：
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，它会告知已生成所有解并回到“第一个”解（对于您想使用的任何第一个定义，可能是按字典顺序，但不需要这样）。我找到的最相关算法是Knuth的《计算机程序设计艺术》第4卷第1部分第7.2.1.5节（第430页）中的M算法。然而，该算法生成所有可能的多重集合划分。书中还有一个练习（7.2.1.5.69，p.778上的解决方案），说明如何修改Alg.M以仅生成最多具有r个分区的解。然而，这仍然允许不同大小的分区（例如，对于r = 2，[[1,2,2]，[1]]将是有效输出）。
有关如何处理此问题的任何想法/技巧/现有算法？请注意，解决方案应高效，即跟踪先前生成的所有解，确定当前生成的解是否为排列，如果是则跳过它，由于随着更多重复项的较长输入的解空间爆炸的速度，这是不可行的。