生成数量有限的数字组合/集合列表 [英] generate a list of combinations/sets of numbers with limited supplies
问题描述
说我有1个红球，1个蓝球，2个黄球和3个绿球，总共7个球。
Say I have 1 red ball, 1 blue ball, 2 yellow balls, and 3 green balls, for a total of 7 balls.
我要选择3个七人一组的球。
I want to select 3 balls from the group of seven. How many ways can I do this?
我手动计数时有11种组合/套。即 123 124 133 134 144 233 234 244 334 344 444
When I counted manually I got 11 combinations/sets. ie 123 124 133 134 144 233 234 244 334 344 444
什么是生成和显示所有内容的有效方法这些组合/集？
What is an efficient way to generate and display all these combinations/sets?
请注意唯一性适用，因此（黄色，红色，黄色）=（黄色，黄色，红色）
Note that uniqueness applies, so (yellow, red, yellow) = (yellow, yellow, red)
推荐答案
第二点，我建议使用生成函数方法。
On second though, I suggest a generating function approach.
- 红球的数量可以是：
0,1 - 蓝色球可以是：
0,1 - 黄色球的数量可以是：
0,1， 2 - 绿球的数量可以是：
0,1,2,3
- The number of red balls can be:
0,1 - The number of blue balls can be:
0,1 - The number of yellow balls can be:
0,1,2 - The number of green balls can be:
0,1,2,3
因此，您想扩展以下多项式
Therefore you want to expand the following polynomial
(1 + x) * (1 + x) * (1 + x + x^2) * (1 + x + x^2 + x^3)
并查看 x ^ 3 的系数，因为您想要总计 3 个球。
and look at the coefficient of x^3 because you want a total of 3 balls.
这将为您提供多种方法，并从每个带括号的表达式中取一个项来获取系数，该方法将告诉您如何组合。之所以有效，是因为选择 0 或 1 红球与选择 1 或 x 分别来自第一个项（1 + x），并类似地选择 i 绿球表示从上一个术语中选择术语 x ^ i 。然后，所选球的总数就是指数的总和。由于您想要 3 个球，因此扩展此多项式时，应查看 x ^ 3 的系数：
This will give you the number of ways to do it, and the way to get the coefficient, taking one term from each parenthesized expression, will tell you how to do the combinations. This works because choosing 0 or 1 red ball is the same as choosing 1 or x from the first term (1 + x), respectively, and similarly choosing i green balls means choosing the term x^i from the last term. Then the total number of balls selected is the sum of the exponents. Since you want 3 balls, you should look at the coefficient of x^3 when this polynomial is expanded:
1 + 4x + 8x^2 + 11x^3 + 11x^4 + 8x^5 + 4x^6 + x^7
因此，存在 11 个可能的<$给定集合中的c $ c> 3 个球。
Therefore there are 11 possible combinations of 3 balls from the given set.
要迭代可能性，您可以从表达式中按顺序选择一个术语：
To iterate the possibilities, you can just choose a term from the expressions in order:
int count = 0;
for (int r=0; r<=1 && r<=3; ++r) {
for (int b=0; b<=1 && r+b<=3; ++b) {
for (int y=0; y<=2 && r+b+y<=3 ; ++y) {
for (int g=0; g<=3 && r+b+y+g==3; ++g) {
count++;
printf(" red: %d\n blue: %d\nyellow: %d\n green: %d",r,b,y,g);
}
}
}
}
return count;
前两个中的第二个条件在此示例中，不需要循环（ r< = 3 和 r + b< = 3 ），但我将其保留了下来来说明如何概括该问题。
The second conditions in the first two for loops (r<=3 and r+b<=3) are unnecessary in this example, but I left it in to illustrate how the problem could be generalized.
这篇关于生成数量有限的数字组合/集合列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
