计算组合数
通常来说,确定一个特定集合的组合数是相当简单的。然而,将其扩展到多重集合,其中每个元素重复出现特定次数,则相对更加困难且文献资料较少。@WorldSEnder提供了一个数学/堆栈交换答案链接,其中包含一个评论,其中有一篇名为Combinatorial Generation的精彩组合学文章,作者是Frank Ruskey。如果您前往第71页,就会发现有一节更严格地讨论了这个主题。
基本定义
- 集合 - 由不同的对象组成的一个集合。
- 例如,
{a, b}
与{a, a, b}
相同,其基数均为2。
- 多重集合 - 类似于集合,但允许重复条目。
- 例如,
{a, b}
和{a, a, b}
是基数分别为2和3的不同多重集合。
- 二项式系数 - 给出了一个n元集合的k个元素子集的数量。
- 多重集合系数/数字 - 具有从有限集中取出的元素的基数k的多重集合的数量。
误解
有一种观点认为存在一个简单的公式可以快速计算长度为k、每个元素重复特定次数的多重集合的组合数(请参见上面高投票的评论)。下面,我们检查每种众所周知的方法。
让我们从二项式系数的一般应用开始。我们立即看到这将失败,因为它严格意味着计算一个“集合”的组合数,其中不允许重复条目。在我们的情况下,允许重复。
继续阅读维基百科页面下面的“
Number of combinations with repetition”部分。这看起来很有前途,因为我们确实有一些复制。我们还看到了一个修改过的二项式系数,似乎更有前途。仔细一看,我们发现这也会失败,因为这严格适用于多重集合,其中每个元素重复最多
k次。
最后,我们尝试使用
multiset coefficient。列出的示例之一与我们要完成的非常相似。
“首先,考虑表示多重集合的符号,该符号表示为 {a、a、a、a、a、a、b、b、c、c、c、d、d、d、d、d、d、d}(6个a,2个b,3个c,7个d):”
这看起来是我们所要推导的一个好的候选对象。但是你会发现,他们继续推导如何从由四个不同元素构成的集合中构造基数为18的多重集合的数量。 这等价于长度为4的18的
整数构成的数量。例如:
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;
}
使用修改后的帕斯卡三角形进行解释
传统帕斯卡三角形(以下简称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个组合的数量(枚举由读者完成)。
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
我应该如何理解这个?每一行的数字都是前一行数字的组合。但是怎么组合呢?…
我们可以根据每个元素的频率来确定。
例如,为了得到第三行代表选择
v2
其中
1-6
的组合数(忽略第一个1),我们查看第二行。由于第三个元素的频率为3,我们将上一行中小于等于此列的所有元素相加(就像使用二项式系数寻找具有不同元素的集合的组合数一样,我们将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.
确实,我们得到了v3
的正确数量的k组合。
示例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个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
。
基准测试:
这里是一个ideone链接,演示了新算法的加速情况。对于向量{4, 2, 6, 4, 9, 8, 2, 4, 1, 1, 6, 9}
,原始版本的计时为2285718
个时钟周期,而上面的算法仅用8
个时钟周期完成,总加速比为2285728 / 8 = 285714.75
...快了十万倍以上。它们都返回相同数量的组合(即122)。大部分速度提升来自于避免显式地生成任何组合(或者像OP的代码一样生成排列)。
{1, 0.5}
和{0.5, 1}
是相同的组合。如果顺序很重要,则称为排列。 - François Andrieuxnums = {1,2,3,4}
,{1,1}
是否是有效的输出?因为这通常表示重复。 - Daniel Langr