我一直在试图找出一种方法来生成多重集的所有不同的大小为 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 位位置的输入向量的元素，从这些位集创建分区。

为了生成下一个分区，我以相反的顺序迭代位集。计算下一个位集排列（使用与 Gosper 的 hack 相反的方法）。如果当前位集中的第一位未设置（即未选择向量索引 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]]

IE。代码的工作原理有点像std::next_permutation，通知它已经生成了所有解决方案，并回到了“第一个”解决方案（对于您想要使用的第一个定义，可能按字典顺序，但不需要如此）。

我发现的最相关的算法是 Knuth 的《计算机编程艺术》第 4 卷第 1 部分第 7.2.1.5 节（第 430 页）中的算法 M。但是，这会生成所有可能的多重集分区。书中还有一个关于如何修改Alg的练习（7.2.1.5.69，第778页的解决方案）。 M，以便仅生成最多具有 r 个分区的解决方案。但是，这仍然允许不同大小的分区（例如[[1, 2, 2], [1]]r = 2 时将是有效输出）。

关于如何解决这个问题有什么想法/技巧/现有算法吗？请注意，该解决方案应该是高效的，即跟踪所有先前生成的解决方案，确定当前生成的解决方案是否是一种排列，如果是，则跳过它，这是不可行的，因为解决方案空间会随着更长的输入而爆炸。重复。

逐一分配元素的递归算法可以基于一些简单的规则：

• 首先对不同元素进行排序或计数；它们不必按任何特定顺序，您只需将相同的元素分组在一起即可。 （此步骤将简化以下一些步骤，但可以跳过。）

   {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 实现，它给出了正确的输出。