生成所有多集size-n分区的算法

Question

我一直在尝试找出一种生成多集的所有不同的size-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]]

不是某种BTW的作业。我在工作时编写代码时遇到了这个问题，但是现在我想知道如何处理这个问题已经出于个人利益。与工作有关的问题的参数足够小，以至于生成数千个重复的解决方案并不重要。

当前解决方案(生成重复项)

为了说明我不仅在没有尝试提出解决方案的情况下提问，让我尝试解释我当前的算法(与多集一起使用时会生成重复的解决方案)。

它的工作方式如下:状态具有一个位集，其中每个分区块的n位设置为1。比特集的长度是size(input) - n * index_block()，例如如果输入向量有8个元素且n = 2，则第一个分区块使用2位设置为1的8位位集，下一个分区块使用2位设置为1的6位位集，依此类推。

通过依次迭代每个位集并提取索引等于当前位集中1位位置的输入矢量元素，可以从这些位集中创建分区。

为了生成下一个分区，我以相反的顺序遍历了位集。计算下一个位集排列(使用Gosper的破解方法)。如果未设置当前位集中的第一位(即未选择矢量索引0)，则该位集将重置为其初始状态。强制始终设置第一位可防止在创建大小为n的set分区时产生重复项(上面显示的第二种重复项)。如果当前位集等于其起始值，则对先前(较长)位集重复此步骤。

这对于集合非常有用(而且非常快)。但是，当与多集一起使用时，它会生成重复的解，因为它不知道两个元素在输入向量中都出现多次。这是一些示例输出:

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，通知已生成所有解决方案，并返回到“第一个”解决方案(对于您要使用的first的任何定义，可能是按字典顺序，但不必如此)。

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

关于如何执行此操作的任何想法/技巧/现有算法？请注意，解决方案应该是高效的，即跟踪所有先前生成的解决方案，弄清当前生成的解决方案是否是排列，如果是这样，则不可行，因为解决方案空间爆炸的速率对于更长的输入(更多)而言是不可行的。重复。

Answer 1

可以基于一些简单的规则来递归地分配元素的递归算法:

首先对不同元素进行排序或计数；它们不必按任何特定顺序排列，您只想将相同的元素组合在一起。 (此步骤将简化以下某些步骤，但可以跳过。)

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