重复组合的计数
Count of combinations with repetitions
我有一种非常低效的方法来计算大小为 N 的数组中 N/2 项的组合。我所做的是首先对数组进行排序，然后遍历数组的排列，用一半的元素创建多重集并将其插入到一个集合中。最后我得到了集合的计数。
long GetCombinations(std::vector<double> nums) {
long combinations = 0;
std::sort(nums.begin(), nums.end());
std::set<std::multiset<double>> super_set;
do {
std::multiset<double> multi_set;
for (unsigned int i = 0; i < nums.size() / 2; ++i)
multi_set.insert(nums[i]);
auto el = (super_set.insert(multi_set));
if (el.second)
++combinations;
} while (std::next_permutation(nums.begin(), nums.end()));
return combinations;
}
代码有效，但效率很低。对于给定的数组 [0.5, 0.5, 1, 1] ，有 3 种大小为 2 的组合：
0.5, 0.5
1, 1
1, 0.5
是否有不同的算法或方法可以提高此代码的速度？
计算组合
一般来说，确定特定集合的组合数量非常简单。然而，将其扩展到每个元素重复特定次数的多重集要困难得多，而且没有很好的记录。 @WorldSEnder linked 到一个 math/stackexchange 的答案，这个答案有 Frank Ruskey 的 comment with a link to this wonderful article in combinatorics called Combinatorial Generation。如果您转到第 71 页，有一个部分更严格地处理这个主题。
基本定义
- 集合 - 不同 对象的集合。
- 例如
{a, b} 与 {a, a, b} 相同，并且都具有基数 2
- 多集 - 类似于集，但允许重复条目。
- 例如
{a, b} 和 {a, a, b} 是基数分别为 2 和 3 的不同多重集
- 二项式系数 - 给出n-元素集的k-元素子集的数量。
- Multiset Coefficient/Number - 基数 k 的多集数，元素取自有限集。
误解
人们相信有一个简单的公式可以快速计算长度为 k 的多重集的组合数，其中每个元素重复特定次数（请参阅上面高度评价的评论）。下面，我们将检查每个众所周知的方法。
先从二项式系数的一般应用说起。我们立即看到这将失败，因为它严格用于计算 set 的组合数，其中不允许重复条目。在我们的例子中，允许重复。
进一步阅读维基百科页面，有一个名为 Number of combinations with repetition 的部分。这看起来很有希望，因为我们确实有 一些 复制。我们还看到了修改后的二项式系数，这似乎更有希望。仔细观察会发现这也会失败，因为这严格适用于每个元素重复最多 k 次的多重集。
最后，我们试试multiset coefficient。列出的示例之一看起来与我们正在尝试完成的非常相似。
"First, consider the notation for multisets that would represent {a, a, a, a, a, a, b, b, c, c, c, d, d, d, d, d, d, d} (6 as, 2 bs, 3 cs, 7 ds) in this form:"
这看起来很适合我们要推导的内容。但是，您会看到他们继续推导出可以从一组 4 个不同元素构建基数 18 的多重集的方法数。这相当于长度为4的18的integer compositions的个数。例如
18 + 0 + 0 + 0
17 + 1 + 0 + 0
16 + 2 + 0 + 0
.
.
.
5 + 4 + 6 + 3
4 + 5 + 6 + 3
3 + 6 + 6 + 3
.
.
.
0 + 1 + 0 + 17
0 + 0 + 1 + 17
0 + 0 + 0 + 18
如您所见，顺序对构图很重要，这显然不适用于我们的情况。
最后提到的两种方法源自著名的 Stars and Bars 简单计数问题方法。据我所知，这种方法不能轻易扩展到我们的案例。
一个可行的算法
unsigned long int getCombinationCount(std::vector<double> nums) {
unsigned long int n = nums.size();
unsigned long int n2 = n / 2;
unsigned long int numUnique = 1;
unsigned long int numCombinations;
std::sort(nums.begin(), nums.end());
std::vector<int> numReps;
double testVal = nums[0];
numReps.push_back(1);
for (std::size_t i = 1; i < n; ++i) {
if (nums[i] != testVal) {
numReps.push_back(1);
testVal = nums[i];
++numUnique;
} else {
++numReps[numUnique - 1];
}
}
int myMax, r = n2 + 1;
std::vector<double> triangleVec(r);
std::vector<double> temp(r);
double tempSum;
myMax = r;
if (myMax > numReps[0] + 1)
myMax = numReps[0] + 1;
for (int i = 0; i < myMax; ++i)
triangleVec[i] = 1;
temp = triangleVec;
for (std::size_t k = 1; k < numUnique; ++k) {
for (int i = n2; i > 0; --i) {
myMax = i - numReps[k];
if (myMax < 0)
myMax = 0;
tempSum = 0;
for (int j = myMax; j <= i; ++j)
tempSum += triangleVec[j];
temp[i] = tempSum;
}
triangleVec = temp;
}
numCombinations = (unsigned long int) triangleVec[n2];
return numCombinations;
}
使用改进的帕斯卡三角形的解释
传统 Pascal's Triangle（从这里开始的 PT）中的条目表示二项式系数，其中三角形的行是您集合中元素的数量，列是您希望的组合长度生成。三角形的构造是我们如何解决手头问题的关键。
如果您注意到对于传统的 PT，要获得特定条目，请说 (i, j) 其中 i 是行和 j 是列，您必须添加条目 (i - 1, j - 1) 和 (i - 1、j)。这是一个例子。
1
1 1
1 2 1 N.B. The first 10 is in the 5th row and 3rd column
1 3 3 1 and is obtained by adding the entries from the
1 4 6 4 1 4th row and 2nd/3rd.
1 5 10 10 5 1
1 6 15 20 15 6 1
我们可以将其扩展到一般多重集，其中每个元素重复特定次数。让我们考虑几个例子。
示例 1：v1 = {1, 2, 2}、v2 = {1, 2, 2, 3, 3, 3} 和 v3 = {1,2,2,3,3,3,4,4,4,4}
下面是 v1 choose 1 - 3 和 v2 choose 1 - 6 的所有可能组合。
[,1] [,1]
[1,] 1 [1,] 1
[2,] 2 [2,] 2
[3,] 3
[,1] [,2] [,1] [,2]
[1,] 1 2 [1,] 1 2
[2,] 2 2 [2,] 1 3
[3,] 2 2
[4,] 2 3
[5,] 3 3
[,1] [,2] [,3] [,1] [,2] [,3]
[1,] 1 2 2 [1,] 1 2 2
[2,] 1 2 3
[3,] 1 3 3
[4,] 2 2 3
[5,] 2 3 3
[6,] 3 3 3
[,1] [,2] [,3] [,4]
[1,] 1 2 2 3
[2,] 1 2 3 3
[3,] 1 3 3 3
[4,] 2 2 3 3
[5,] 2 3 3 3
[,1] [,2] [,3] [,4] [,5]
[1,] 1 2 2 3 3
[2,] 1 2 3 3 3
[3,] 2 2 3 3 3
[,1] [,2] [,3] [,4] [,5] [,6]
[1,] 1 2 2 3 3 3
让我们写下v1和v2的所有k的组合数。
2 2 1
3 5 6 5 3 1
我要给你v3的所有k的组合数（我会留给reader来枚举它们） .
4 9 15 20 22 20 15 9 4 1
我们以一种特殊的方式组合上面的结果，并注意到事情开始看起来非常熟悉。
2 2 1
3 5 6 5 3 1
4 9 15 20 22 20 15 9 4 1
我们添加了几个作为占位符来完成这个修改后的 PT
1 1
1 2 2 1
1 3 5 6 5 3 1
1 4 9 15 20 22 20 15 9 4 1
这是什么意思？很明显，每一行中的数字都是前一行中数字的组合。但是怎么办？....
We let the frequency of each element guide us.
例如，要获取表示 v2 choose 1 - 6 组合数的第三行（忽略第一个 1），我们查看第 2 行。由于第 3 个元素的频率为 3，我们添加4 个元素（3 + 1.. 就像用于查找具有不同元素的集合的组合数的二项式系数一样，我们将 2 个条目加在一起或 1 + 1）在上面的行中，列小于或等于我们的列正在寻找。所以我们有：
if the column index is non-positive or greater than the
number of columns in the previous row, the value is 0
v2 choose 3
(3, 2) = (2, 2 - 3) + (2, 2 - 2) + (2, 2 - 1) + (2, 2 - 0)
= 0 + 0 + 1 + 2
= 3
v2 choose 4
(3, 3) = (2, 3 - 3) + (2, 3 - 2) + (2, 3 - 1) + (2, 3 - 0)
= 0 + 1 + 2 + 2
= 5
v2 choose 5
(3, 4) = (2, 4 - 3) + (2, 4 - 2) + (2, 4 - 1) + (2, 4 - 0)
= 1 + 2 + 2 + 1
= 6
v2 choose 6 outside of range
(3, 5) = (2, 5 - 3) + (2, 5 - 2) + (2, 5 - 1) + (2, 5 - 0)
= 2 + 2 + 1 + 0
= 5
etc.
继续这个逻辑，让我们看看是否可以获得v3的k-组合的数量。由于第 4 个元素的频率是 4，我们需要将 5 个条目加在一起。
v3 choose 3
(4, 2) = (3, 2 - 4) + (3, 2 - 3) + (3, 2 - 2) + (3, 2 - 1) + (3, 2 - 0)
= 0 + 0 + 0 + 1 + 3
= 4
v3 choose 4
(4, 3) = (3, 3 - 4) + (3, 3 - 3) + (3, 3 - 2) + (3, 3 - 1) + (3, 3 - 0)
= 0 + 0 + 1 + 3 + 5
= 9
v3 choose 5
(4, 4) = (3, 4 - 4) + (3, 4 - 3) + (3, 4 - 2) + (3, 4 - 1) + (3, 4 - 0)
= 0 + 1 + 3 + 5 + 6
= 15
v3 choose 6
(4, 5) = (3, 5 - 4) + (3, 5 - 3) + (3, 5 - 2) + (3, 5 - 1) + (3, 5 - 0)
= 1 + 3 + 5 + 6 + 5
= 20
etc.
事实上，我们确实得到了 k 的正确数量 - v3.
的组合
示例 2：z1 = {1,1,1,2}、z2 = {1,1,1,1,2,3,3,3,3,3} 和 z3 = {1,1,1,1,2,3,3,3,3,3,4,4}
您会注意到我们正在构造这些向量，使得每个连续的向量都包含先前的向量。我们这样做是为了能够正确构建修改后的 PT。这类似于传统的 PT，其中对于每个连续的行，我们只是将一个数字添加到前一行。这些向量的修改后的 PT 是：
1 1 1 1
1 2 2 2 1
1 3 5 7 8 8 7 5 3 1
1 4 9 15 20 23 23 20 15 9 4 1
让我们构建z2 choose 6和z3 choose 9，看看我们是否正确：
z2 choose 6
[,1] [,2] [,3] [,4] [,5] [,6]
[1,] 1 1 1 2 3 3
[2,] 1 1 1 3 3 3 This shows that we produce 7 combs
[3,] 1 1 2 3 3 3 just as predicted by our modified
[4,] 1 1 3 3 3 3 PT (i.e. entry (3, 6 + 1) = 7)
[5,] 1 2 3 3 3 3
[6,] 1 3 3 3 3 3
[7,] 2 3 3 3 3 3
z3 choose 9
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
[1,] 1 1 1 2 3 3 3 3 3
[2,] 1 1 1 2 3 3 3 3 4
[3,] 1 1 1 2 3 3 3 4 4 This shows that we produce 9
[4,] 1 1 1 3 3 3 3 3 4 combs just as predicted by
[5,] 1 1 1 3 3 3 3 4 4 our modified PT (i.e. entry
[6,] 1 1 2 3 3 3 3 3 4 (4, 9 + 1) = 9)
[7,] 1 1 2 3 3 3 3 4 4
[8,] 1 1 3 3 3 3 3 4 4
[9,] 1 2 3 3 3 3 3 4 4
快速说明一下，第一行占位符类似于传统 PT 的第二行（即 1 1）。粗略地说（请参阅边缘情况的代码），如果第一个元素的频率为 m，则修改后的 PT 的第一行将包含 m + 1个。
没有通用公式的原因（例如类似于二项式系数的东西）
从上面两个例子可以看出，修改后的PT是基于特定的多重集，因此不能泛化。即使您考虑由相同的不同元素组成的特定基数的多重集，修改后的 PT 也会有所不同。例如，多重集 a = {1, 2, 2, 3, 3, 3} 和 b = {1, 1, 2, 2, 3, 3} 分别生成以下修改后的 PT：
1 1
1 2 2 1
1 3 5 6 5 3 1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
请注意 a choose 2 = 5 而 b choose 2 = 6.
基准：
这里是 link 到 ideone 演示新算法的加速。对于矢量 {4, 2, 6, 4, 9, 8, 2, 4, 1, 1, 6, 9}，原始时间是 2285718 个时钟滴答，而上面的算法在 8 个时钟滴答中完成，总加速 2285728 / 8 = 285714.75...快十万倍。它们都 return 相同数量的组合（即 122）。大多数速度增益来自于避免显式生成任何组合（或像 OP 代码那样的排列）。
我有一种非常低效的方法来计算大小为 N 的数组中 N/2 项的组合。我所做的是首先对数组进行排序，然后遍历数组的排列，用一半的元素创建多重集并将其插入到一个集合中。最后我得到了集合的计数。
long GetCombinations(std::vector<double> nums) {
long combinations = 0;
std::sort(nums.begin(), nums.end());
std::set<std::multiset<double>> super_set;
do {
std::multiset<double> multi_set;
for (unsigned int i = 0; i < nums.size() / 2; ++i)
multi_set.insert(nums[i]);
auto el = (super_set.insert(multi_set));
if (el.second)
++combinations;
} while (std::next_permutation(nums.begin(), nums.end()));
return combinations;
}
代码有效，但效率很低。对于给定的数组 [0.5, 0.5, 1, 1] ，有 3 种大小为 2 的组合：
0.5, 0.5
1, 1
1, 0.5
是否有不同的算法或方法可以提高此代码的速度？
计算组合
一般来说，确定特定集合的组合数量非常简单。然而，将其扩展到每个元素重复特定次数的多重集要困难得多，而且没有很好的记录。 @WorldSEnder linked 到一个 math/stackexchange 的答案，这个答案有 Frank Ruskey 的 comment with a link to this wonderful article in combinatorics called Combinatorial Generation。如果您转到第 71 页，有一个部分更严格地处理这个主题。
基本定义
- 集合 - 不同 对象的集合。
- 例如
{a, b}与{a, a, b}相同，并且都具有基数 2 - 多集 - 类似于集，但允许重复条目。
- 例如
{a, b}和{a, a, b}是基数分别为 2 和 3 的不同多重集 - 二项式系数 - 给出n-元素集的k-元素子集的数量。
- Multiset Coefficient/Number - 基数 k 的多集数，元素取自有限集。
误解
人们相信有一个简单的公式可以快速计算长度为 k 的多重集的组合数，其中每个元素重复特定次数（请参阅上面高度评价的评论）。下面，我们将检查每个众所周知的方法。
先从二项式系数的一般应用说起。我们立即看到这将失败，因为它严格用于计算 set 的组合数，其中不允许重复条目。在我们的例子中，允许重复。
进一步阅读维基百科页面，有一个名为 Number of combinations with repetition 的部分。这看起来很有希望，因为我们确实有 一些 复制。我们还看到了修改后的二项式系数，这似乎更有希望。仔细观察会发现这也会失败，因为这严格适用于每个元素重复最多 k 次的多重集。
最后，我们试试multiset coefficient。列出的示例之一看起来与我们正在尝试完成的非常相似。
"First, consider the notation for multisets that would represent {a, a, a, a, a, a, b, b, c, c, c, d, d, d, d, d, d, d} (6 as, 2 bs, 3 cs, 7 ds) in this form:"
这看起来很适合我们要推导的内容。但是，您会看到他们继续推导出可以从一组 4 个不同元素构建基数 18 的多重集的方法数。这相当于长度为4的18的integer compositions的个数。例如
18 + 0 + 0 + 0
17 + 1 + 0 + 0
16 + 2 + 0 + 0
.
.
.
5 + 4 + 6 + 3
4 + 5 + 6 + 3
3 + 6 + 6 + 3
.
.
.
0 + 1 + 0 + 17
0 + 0 + 1 + 17
0 + 0 + 0 + 18
如您所见，顺序对构图很重要，这显然不适用于我们的情况。
最后提到的两种方法源自著名的 Stars and Bars 简单计数问题方法。据我所知，这种方法不能轻易扩展到我们的案例。
一个可行的算法
unsigned long int getCombinationCount(std::vector<double> nums) {
unsigned long int n = nums.size();
unsigned long int n2 = n / 2;
unsigned long int numUnique = 1;
unsigned long int numCombinations;
std::sort(nums.begin(), nums.end());
std::vector<int> numReps;
double testVal = nums[0];
numReps.push_back(1);
for (std::size_t i = 1; i < n; ++i) {
if (nums[i] != testVal) {
numReps.push_back(1);
testVal = nums[i];
++numUnique;
} else {
++numReps[numUnique - 1];
}
}
int myMax, r = n2 + 1;
std::vector<double> triangleVec(r);
std::vector<double> temp(r);
double tempSum;
myMax = r;
if (myMax > numReps[0] + 1)
myMax = numReps[0] + 1;
for (int i = 0; i < myMax; ++i)
triangleVec[i] = 1;
temp = triangleVec;
for (std::size_t k = 1; k < numUnique; ++k) {
for (int i = n2; i > 0; --i) {
myMax = i - numReps[k];
if (myMax < 0)
myMax = 0;
tempSum = 0;
for (int j = myMax; j <= i; ++j)
tempSum += triangleVec[j];
temp[i] = tempSum;
}
triangleVec = temp;
}
numCombinations = (unsigned long int) triangleVec[n2];
return numCombinations;
}
使用改进的帕斯卡三角形的解释
传统 Pascal's Triangle（从这里开始的 PT）中的条目表示二项式系数，其中三角形的行是您集合中元素的数量，列是您希望的组合长度生成。三角形的构造是我们如何解决手头问题的关键。
如果您注意到对于传统的 PT，要获得特定条目，请说 (i, j) 其中 i 是行和 j 是列，您必须添加条目 (i - 1, j - 1) 和 (i - 1、j)。这是一个例子。
1
1 1
1 2 1 N.B. The first 10 is in the 5th row and 3rd column
1 3 3 1 and is obtained by adding the entries from the
1 4 6 4 1 4th row and 2nd/3rd.
1 5 10 10 5 1
1 6 15 20 15 6 1
我们可以将其扩展到一般多重集，其中每个元素重复特定次数。让我们考虑几个例子。
示例 1：v1 = {1, 2, 2}、v2 = {1, 2, 2, 3, 3, 3} 和 v3 = {1,2,2,3,3,3,4,4,4,4}
下面是 v1 choose 1 - 3 和 v2 choose 1 - 6 的所有可能组合。
[,1] [,1]
[1,] 1 [1,] 1
[2,] 2 [2,] 2
[3,] 3
[,1] [,2] [,1] [,2]
[1,] 1 2 [1,] 1 2
[2,] 2 2 [2,] 1 3
[3,] 2 2
[4,] 2 3
[5,] 3 3
[,1] [,2] [,3] [,1] [,2] [,3]
[1,] 1 2 2 [1,] 1 2 2
[2,] 1 2 3
[3,] 1 3 3
[4,] 2 2 3
[5,] 2 3 3
[6,] 3 3 3
[,1] [,2] [,3] [,4]
[1,] 1 2 2 3
[2,] 1 2 3 3
[3,] 1 3 3 3
[4,] 2 2 3 3
[5,] 2 3 3 3
[,1] [,2] [,3] [,4] [,5]
[1,] 1 2 2 3 3
[2,] 1 2 3 3 3
[3,] 2 2 3 3 3
[,1] [,2] [,3] [,4] [,5] [,6]
[1,] 1 2 2 3 3 3
让我们写下v1和v2的所有k的组合数。
2 2 1
3 5 6 5 3 1
我要给你v3的所有k的组合数（我会留给reader来枚举它们） .
4 9 15 20 22 20 15 9 4 1
我们以一种特殊的方式组合上面的结果，并注意到事情开始看起来非常熟悉。
2 2 1
3 5 6 5 3 1
4 9 15 20 22 20 15 9 4 1
我们添加了几个作为占位符来完成这个修改后的 PT
1 1
1 2 2 1
1 3 5 6 5 3 1
1 4 9 15 20 22 20 15 9 4 1
这是什么意思？很明显，每一行中的数字都是前一行中数字的组合。但是怎么办？....
We let the frequency of each element guide us.
例如，要获取表示 v2 choose 1 - 6 组合数的第三行（忽略第一个 1），我们查看第 2 行。由于第 3 个元素的频率为 3，我们添加4 个元素（3 + 1.. 就像用于查找具有不同元素的集合的组合数的二项式系数一样，我们将 2 个条目加在一起或 1 + 1）在上面的行中，列小于或等于我们的列正在寻找。所以我们有：
if the column index is non-positive or greater than the
number of columns in the previous row, the value is 0
v2 choose 3
(3, 2) = (2, 2 - 3) + (2, 2 - 2) + (2, 2 - 1) + (2, 2 - 0)
= 0 + 0 + 1 + 2
= 3
v2 choose 4
(3, 3) = (2, 3 - 3) + (2, 3 - 2) + (2, 3 - 1) + (2, 3 - 0)
= 0 + 1 + 2 + 2
= 5
v2 choose 5
(3, 4) = (2, 4 - 3) + (2, 4 - 2) + (2, 4 - 1) + (2, 4 - 0)
= 1 + 2 + 2 + 1
= 6
v2 choose 6 outside of range
(3, 5) = (2, 5 - 3) + (2, 5 - 2) + (2, 5 - 1) + (2, 5 - 0)
= 2 + 2 + 1 + 0
= 5
etc.
继续这个逻辑，让我们看看是否可以获得v3的k-组合的数量。由于第 4 个元素的频率是 4，我们需要将 5 个条目加在一起。
v3 choose 3
(4, 2) = (3, 2 - 4) + (3, 2 - 3) + (3, 2 - 2) + (3, 2 - 1) + (3, 2 - 0)
= 0 + 0 + 0 + 1 + 3
= 4
v3 choose 4
(4, 3) = (3, 3 - 4) + (3, 3 - 3) + (3, 3 - 2) + (3, 3 - 1) + (3, 3 - 0)
= 0 + 0 + 1 + 3 + 5
= 9
v3 choose 5
(4, 4) = (3, 4 - 4) + (3, 4 - 3) + (3, 4 - 2) + (3, 4 - 1) + (3, 4 - 0)
= 0 + 1 + 3 + 5 + 6
= 15
v3 choose 6
(4, 5) = (3, 5 - 4) + (3, 5 - 3) + (3, 5 - 2) + (3, 5 - 1) + (3, 5 - 0)
= 1 + 3 + 5 + 6 + 5
= 20
etc.
事实上，我们确实得到了 k 的正确数量 - v3.
示例 2：z1 = {1,1,1,2}、z2 = {1,1,1,1,2,3,3,3,3,3} 和 z3 = {1,1,1,1,2,3,3,3,3,3,4,4}
您会注意到我们正在构造这些向量，使得每个连续的向量都包含先前的向量。我们这样做是为了能够正确构建修改后的 PT。这类似于传统的 PT，其中对于每个连续的行，我们只是将一个数字添加到前一行。这些向量的修改后的 PT 是：
1 1 1 1
1 2 2 2 1
1 3 5 7 8 8 7 5 3 1
1 4 9 15 20 23 23 20 15 9 4 1
让我们构建z2 choose 6和z3 choose 9，看看我们是否正确：
z2 choose 6
[,1] [,2] [,3] [,4] [,5] [,6]
[1,] 1 1 1 2 3 3
[2,] 1 1 1 3 3 3 This shows that we produce 7 combs
[3,] 1 1 2 3 3 3 just as predicted by our modified
[4,] 1 1 3 3 3 3 PT (i.e. entry (3, 6 + 1) = 7)
[5,] 1 2 3 3 3 3
[6,] 1 3 3 3 3 3
[7,] 2 3 3 3 3 3
z3 choose 9
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
[1,] 1 1 1 2 3 3 3 3 3
[2,] 1 1 1 2 3 3 3 3 4
[3,] 1 1 1 2 3 3 3 4 4 This shows that we produce 9
[4,] 1 1 1 3 3 3 3 3 4 combs just as predicted by
[5,] 1 1 1 3 3 3 3 4 4 our modified PT (i.e. entry
[6,] 1 1 2 3 3 3 3 3 4 (4, 9 + 1) = 9)
[7,] 1 1 2 3 3 3 3 4 4
[8,] 1 1 3 3 3 3 3 4 4
[9,] 1 2 3 3 3 3 3 4 4
快速说明一下，第一行占位符类似于传统 PT 的第二行（即 1 1）。粗略地说（请参阅边缘情况的代码），如果第一个元素的频率为 m，则修改后的 PT 的第一行将包含 m + 1个。
没有通用公式的原因（例如类似于二项式系数的东西）
从上面两个例子可以看出，修改后的PT是基于特定的多重集，因此不能泛化。即使您考虑由相同的不同元素组成的特定基数的多重集，修改后的 PT 也会有所不同。例如，多重集 a = {1, 2, 2, 3, 3, 3} 和 b = {1, 1, 2, 2, 3, 3} 分别生成以下修改后的 PT：
1 1
1 2 2 1
1 3 5 6 5 3 1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
请注意 a choose 2 = 5 而 b choose 2 = 6.
基准：
这里是 link 到 ideone 演示新算法的加速。对于矢量 {4, 2, 6, 4, 9, 8, 2, 4, 1, 1, 6, 9}，原始时间是 2285718 个时钟滴答，而上面的算法在 8 个时钟滴答中完成，总加速 2285728 / 8 = 285714.75...快十万倍。它们都 return 相同数量的组合（即 122）。大多数速度增益来自于避免显式生成任何组合（或像 OP 代码那样的排列）。