生成所有 multiset size-n 分区的算法
Algorithm to generate all multiset size-n partitions
我一直在尝试找出一种方法来生成多重集的所有不同的大小为 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 位位置的输入向量的元素，从这些位集创建一个分区。
为了生成下一个分区，我以相反的顺序遍历位集。计算下一个 bitset 排列（使用 Gosper 的 hack 的反向）。如果当前位集中的第一位未设置（即向量索引 0 不是 selected），则该位集将重置为其起始状态。强制始终设置第一位可防止在创建大小为 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]]
最后一个（重复的）解决方案的生成仅仅是因为算法不知道输入中的重复项，它在两个示例中生成完全相同的内部状态（即 select 的索引）。
想要的解决方案
我想现在我想要得到的结果已经很清楚了。为了完整起见，它看起来有点像下面这样：
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，通知它已生成所有解决方案并返回到 "first" 解决方案（对于您要使用的 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 的有效输出）。
有什么 ideas/tricks/existing 算法可以解决这个问题吗？请注意，解决方案应该是高效的，即跟踪所有先前生成的解决方案，确定当前生成的解决方案是否是排列，如果是，则跳过它，这是不可行的，因为解决方案 space 爆炸的速度更长的输入，更多的重复。
这是我的纸笔算法：
Describe the multiset in item quantities, e.g., {(1,2),(2,2)}
f(multiset,result):
if the multiset is empty:
return result
otherwise:
call f again with each unique distribution of one element added to result and
removed from the multiset state
Example:
{(1,2),(2,2),(3,2)} n = 2
11 -> 11 22 -> 11 22 33
11 2 2 -> 11 23 23
1 1 -> 12 12 -> 12 12 33
12 1 2 -> 12 13 23
Example:
{(1,2),(2,2),(3,2)} n = 3
11 -> 112 2 -> 112 233
11 22 -> 113 223
1 1 -> 122 1 -> 122 133
12 12 -> 123 123
让我们来解决m69在下面评论的处理潜在重复分布的问题：
{A,B,B,C,C,D,D,D,D}
We've reached {A, , }{B, , }{B, , }, have 2 C's to distribute
and we'd like to avoid `ac bc b` generated along with `ac b bc`.
Because our generation in the level just above is ordered, the series of identical
counts will be continuous. When a series of identical counts is encountered, make
the assignment for the whole block of identical counts (rather than each one),
and partition that contribution in descending parts; for example,
| identical |
ac b b
ac bc b // descending parts [1,0]
Example of longer block:
| identical block | descending parts
ac bcccc b b b // [4,0,0,0]
ac bccc bc b b // [3,1,0,0]
ac bcc bcc b b // [2,2,0,0]
...
逐个分配元素的递归算法可以基于一些简单的规则：
- 首先对不同的元素进行排序或计数；它们不必按任何特定顺序排列，您只需将相同的元素组合在一起即可。 （此步骤将简化后面的一些步骤，但可以跳过。）
{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^
- 将元素插入每个可用的非重复块space：
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 实现，它给出了正确的输出。
这是一个有效的解决方案，它使用 herve 命名空间内的 N2639. The comments should make it pretty self-explanatory. The "herve/combinatorics.hpp" file contains the code listed in N2639 中的 Hervé Brönnimann 提出的 next_combination 函数。它在 C++11/14 中，转换为较旧的标准应该非常简单。
请注意，我只是快速测试了解决方案。此外，几分钟前我从基于 class 的实现中提取了它，因此可能会出现一些额外的错误。快速初始测试似乎可以确认它有效，但可能存在一些极端情况惯于。
#include <cstdint>
#include <iterator>
#include "herve/combinatorics.hpp"
template <typename BidirIter>
bool next_combination_partition (BidirIter const & startIt,
BidirIter const & endIt, uint32_t const groupSize) {
// Typedefs
using tDiff = typename std::iterator_traits<BidirIter>::difference_type;
// Skip the last partition, because is consists of the remaining elements.
// Thus if there's 2 groups or less, the start should be at position 0.
tDiff const totalLength = std::distance(startIt, endIt);
uint32_t const numTotalGroups = std::max(static_cast<uint32_t>((totalLength - 1) / groupSize + 1), 2u);
uint32_t curBegin = (numTotalGroups - 2) * groupSize;
uint32_t const lastGroupBegin = curBegin - 1;
uint32_t curMid = curBegin + groupSize;
bool atStart = (totalLength != 0);
// Iterate over combinations from back of list to front. If a combination ends
// up at its starting value, update the previous one as well.
for (; (curMid != 0) && (atStart);
curMid = curBegin, curBegin -= groupSize) {
// To prevent duplicates, first element of each combination partition needs
// to be fixed. So move start iterator to the next element. This is not true
// for the starting (2nd to last) group though.
uint32_t const startIndex = std::min(curBegin + 1, lastGroupBegin + 1);
auto const iterStart = std::next(startIt, startIndex);
auto const iterMid = std::next(startIt, curMid);
atStart = !herve::next_combination(iterStart, iterMid, endIt);
}
return !atStart;
}
编辑下面是我快速拼凑的测试代码（"combopart.hpp"显然是包含上述功能的文件）。
#include "combopart.hpp"
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <vector>
int main (int argc, char* argv[]) {
uint32_t const groupSize = 2;
std::vector<uint32_t> v;
v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
v = {0, 0, 0, 1, 1, 1, 2, 2, 2, 3};
v = {1, 1, 2, 2};
// Make sure contents are sorted
std::sort(v.begin(), v.end());
uint64_t count = 0;
do {
++count;
std::cout << "[ ";
uint32_t elemCount = 0;
for (auto it = v.begin(); it != v.end(); ++it) {
std::cout << *it << " ";
elemCount++;
if ((elemCount % groupSize == 0) && (it != std::prev(v.end()))) {
std::cout << "| ";
}
}
std::cout << "]" << std::endl;
} while (next_combination_partition(v.begin(), v.end(), groupSize));
std::cout << std::endl << "# elements: " << v.size() << " - group size: " <<
groupSize << " - # combination partitions: " << count << std::endl;
return 0;
}
编辑 2 改进算法。将早期退出分支替换为条件移动（使用 std::max）和将 atStart 布尔值设置为 false 的组合。虽然未经测试，但请注意。
编辑 3 需要额外修改，以免 "fix" 倒数第二个分区中的第一个元素。附加代码应该编译为条件移动，因此不应有与之相关的分支成本。
P.S.: 我知道@Howard Hinnant 生成组合的代码（可在 https://howardhinnant.github.io/combinations.html 获得）比 Hervé Brönnimann 的代码快得多。但是，该代码无法处理输入中的重复项（因为据我所知，它甚至从不取消引用迭代器），这是我的问题明确要求的。另一方面，如果您确定您的输入不会包含重复项，那么它绝对是您想要与我上面的函数一起使用的代码。
我一直在尝试找出一种方法来生成多重集的所有不同的大小为 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 位位置的输入向量的元素，从这些位集创建一个分区。
为了生成下一个分区，我以相反的顺序遍历位集。计算下一个 bitset 排列（使用 Gosper 的 hack 的反向）。如果当前位集中的第一位未设置（即向量索引 0 不是 selected），则该位集将重置为其起始状态。强制始终设置第一位可防止在创建大小为 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]]
最后一个（重复的）解决方案的生成仅仅是因为算法不知道输入中的重复项，它在两个示例中生成完全相同的内部状态（即 select 的索引）。
想要的解决方案
我想现在我想要得到的结果已经很清楚了。为了完整起见，它看起来有点像下面这样：
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，通知它已生成所有解决方案并返回到 "first" 解决方案（对于您要使用的 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 的有效输出）。
有什么 ideas/tricks/existing 算法可以解决这个问题吗？请注意，解决方案应该是高效的，即跟踪所有先前生成的解决方案，确定当前生成的解决方案是否是排列，如果是，则跳过它，这是不可行的，因为解决方案 space 爆炸的速度更长的输入，更多的重复。
这是我的纸笔算法：
Describe the multiset in item quantities, e.g., {(1,2),(2,2)}
f(multiset,result):
if the multiset is empty:
return result
otherwise:
call f again with each unique distribution of one element added to result and
removed from the multiset state
Example:
{(1,2),(2,2),(3,2)} n = 2
11 -> 11 22 -> 11 22 33
11 2 2 -> 11 23 23
1 1 -> 12 12 -> 12 12 33
12 1 2 -> 12 13 23
Example:
{(1,2),(2,2),(3,2)} n = 3
11 -> 112 2 -> 112 233
11 22 -> 113 223
1 1 -> 122 1 -> 122 133
12 12 -> 123 123
让我们来解决m69在下面评论的处理潜在重复分布的问题：
{A,B,B,C,C,D,D,D,D}
We've reached {A, , }{B, , }{B, , }, have 2 C's to distribute
and we'd like to avoid `ac bc b` generated along with `ac b bc`.
Because our generation in the level just above is ordered, the series of identical
counts will be continuous. When a series of identical counts is encountered, make
the assignment for the whole block of identical counts (rather than each one),
and partition that contribution in descending parts; for example,
| identical |
ac b b
ac bc b // descending parts [1,0]
Example of longer block:
| identical block | descending parts
ac bcccc b b b // [4,0,0,0]
ac bccc bc b b // [3,1,0,0]
ac bcc bcc b b // [2,2,0,0]
...
逐个分配元素的递归算法可以基于一些简单的规则：
- 首先对不同的元素进行排序或计数；它们不必按任何特定顺序排列，您只需将相同的元素组合在一起即可。 （此步骤将简化后面的一些步骤，但可以跳过。）
{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^
- 将元素插入每个可用的非重复块space：
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 实现，它给出了正确的输出。
这是一个有效的解决方案，它使用 herve 命名空间内的 N2639. The comments should make it pretty self-explanatory. The "herve/combinatorics.hpp" file contains the code listed in N2639 中的 Hervé Brönnimann 提出的 next_combination 函数。它在 C++11/14 中，转换为较旧的标准应该非常简单。
请注意，我只是快速测试了解决方案。此外，几分钟前我从基于 class 的实现中提取了它，因此可能会出现一些额外的错误。快速初始测试似乎可以确认它有效，但可能存在一些极端情况惯于。
#include <cstdint>
#include <iterator>
#include "herve/combinatorics.hpp"
template <typename BidirIter>
bool next_combination_partition (BidirIter const & startIt,
BidirIter const & endIt, uint32_t const groupSize) {
// Typedefs
using tDiff = typename std::iterator_traits<BidirIter>::difference_type;
// Skip the last partition, because is consists of the remaining elements.
// Thus if there's 2 groups or less, the start should be at position 0.
tDiff const totalLength = std::distance(startIt, endIt);
uint32_t const numTotalGroups = std::max(static_cast<uint32_t>((totalLength - 1) / groupSize + 1), 2u);
uint32_t curBegin = (numTotalGroups - 2) * groupSize;
uint32_t const lastGroupBegin = curBegin - 1;
uint32_t curMid = curBegin + groupSize;
bool atStart = (totalLength != 0);
// Iterate over combinations from back of list to front. If a combination ends
// up at its starting value, update the previous one as well.
for (; (curMid != 0) && (atStart);
curMid = curBegin, curBegin -= groupSize) {
// To prevent duplicates, first element of each combination partition needs
// to be fixed. So move start iterator to the next element. This is not true
// for the starting (2nd to last) group though.
uint32_t const startIndex = std::min(curBegin + 1, lastGroupBegin + 1);
auto const iterStart = std::next(startIt, startIndex);
auto const iterMid = std::next(startIt, curMid);
atStart = !herve::next_combination(iterStart, iterMid, endIt);
}
return !atStart;
}
编辑下面是我快速拼凑的测试代码（"combopart.hpp"显然是包含上述功能的文件）。
#include "combopart.hpp"
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <vector>
int main (int argc, char* argv[]) {
uint32_t const groupSize = 2;
std::vector<uint32_t> v;
v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
v = {0, 0, 0, 1, 1, 1, 2, 2, 2, 3};
v = {1, 1, 2, 2};
// Make sure contents are sorted
std::sort(v.begin(), v.end());
uint64_t count = 0;
do {
++count;
std::cout << "[ ";
uint32_t elemCount = 0;
for (auto it = v.begin(); it != v.end(); ++it) {
std::cout << *it << " ";
elemCount++;
if ((elemCount % groupSize == 0) && (it != std::prev(v.end()))) {
std::cout << "| ";
}
}
std::cout << "]" << std::endl;
} while (next_combination_partition(v.begin(), v.end(), groupSize));
std::cout << std::endl << "# elements: " << v.size() << " - group size: " <<
groupSize << " - # combination partitions: " << count << std::endl;
return 0;
}
编辑 2 改进算法。将早期退出分支替换为条件移动（使用 std::max）和将 atStart 布尔值设置为 false 的组合。虽然未经测试，但请注意。
编辑 3 需要额外修改，以免 "fix" 倒数第二个分区中的第一个元素。附加代码应该编译为条件移动，因此不应有与之相关的分支成本。
P.S.: 我知道@Howard Hinnant 生成组合的代码（可在 https://howardhinnant.github.io/combinations.html 获得）比 Hervé Brönnimann 的代码快得多。但是，该代码无法处理输入中的重复项（因为据我所知，它甚至从不取消引用迭代器），这是我的问题明确要求的。另一方面，如果您确定您的输入不会包含重复项，那么它绝对是您想要与我上面的函数一起使用的代码。