and look at the coefficient of x^3 because you want a total of 3 balls.
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
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:
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.
generate_combinations(a1, a2, a3, a4, c1, c2, c3, c4)
1. if a1 + a2 + a3 + a4 = 3 then print (a1, a2, a3, a4)
2. else then
3. if c1 > 0 then generate_combinations(a1+1, a2, a3, a4, c1-1, c2, c3, c4)
4. if c2 > 0 then generate_combinations(a1, a2+1, a3, a4, c1, c2-1, c3, c4)
5. if c3 > 0 then generate_combinations(a1, a2, a3+1, a4, c1, c2, c3-1, c4)
6. if c4 > 0 then generate_combinations(a1, a2, a3, a4+1, c1, c2, c3, c4-1)
Or something like that. That won't catch duplicates, though... I suppose you could add some more logic to filter those out, though. Maybe post-processing?
Some clarification: this works by keeping counts of (1) the balls in your hand and (2) the balls in the bag. It ensures that hand+bag=original for every color. Call it with an initially empty hand and it will print every way you can have three balls in your hand.
If you really want to make sure that the algorithm only gives unique ones (rather than using this in conjunction with an algorithm to remove duplicates from a list), you can make sure that you don't add any e.g. red balls to your hand if you have already added any higher-order balls (i.e., if a2 > 0 and a1 = 0, then you don't need to add any red).
发布评论
评论（2）
其次，我建议采用生成函数方法。
0,10,10,1 ,20,1,2,3因此你想展开下面的多项式
并看看
x^3的系数code> 因为您总共需要3球。这将为您提供执行此操作的多种方法，以及获取系数的方法（从每个括号表达式中取出一项）将告诉您如何进行组合。这是有效的，因为选择
0或1红球与从第一项1或x中选择相同分别为 code>(1 + x)，类似地选择i绿球意味着从最后一项中选择项x^i。那么选出的球总数就是指数之和。由于您想要3个球，因此您应该查看该多项式展开时x^3的系数：因此，有
11种可能的组合给定组中的3个球。要迭代可能性，您只需按顺序从表达式中选择一个术语：
前两个
for循环中的第二个条件（r<=3和r +b<=3) 在此示例中是不必要的，但我将其保留下来是为了说明如何概括该问题。On second though, I suggest a generating function approach.
0,10,10,1,20,1,2,3Therefore you want to expand the following polynomial
and look at the coefficient of
x^3because you want a total of3balls.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
0or1red ball is the same as choosing1orxfrom the first term(1 + x), respectively, and similarly choosingigreen balls means choosing the termx^ifrom the last term. Then the total number of balls selected is the sum of the exponents. Since you want3balls, you should look at the coefficient ofx^3when this polynomial is expanded:Therefore there are
11possible combinations of3balls from the given set.To iterate the possibilities, you can just choose a term from the expressions in order:
The second conditions in the first two
forloops (r<=3andr+b<=3) are unnecessary in this example, but I left it in to illustrate how the problem could be generalized.或者类似的东西。不过，这不会捕获重复项...不过，我想您可以添加更多逻辑来过滤掉这些重复项。也许是后期处理？
一些澄清：这是通过计数（1）你手中的球和（2）袋子中的球来实现的。它确保每种颜色的手+包=原装。最初空手调用它，它会打印出您手中可以有三个球的所有方式。
如果您确实想确保该算法仅给出唯一的球（而不是将其与算法结合使用以从列表中删除重复项），则可以确保您不会将任何例如红球添加到您的手上，如果您已经添加了任何高阶球（即，如果 a2 > 0 且 a1 = 0，则无需添加任何红色）。
Or something like that. That won't catch duplicates, though... I suppose you could add some more logic to filter those out, though. Maybe post-processing?
Some clarification: this works by keeping counts of (1) the balls in your hand and (2) the balls in the bag. It ensures that hand+bag=original for every color. Call it with an initially empty hand and it will print every way you can have three balls in your hand.
If you really want to make sure that the algorithm only gives unique ones (rather than using this in conjunction with an algorithm to remove duplicates from a list), you can make sure that you don't add any e.g. red balls to your hand if you have already added any higher-order balls (i.e., if a2 > 0 and a1 = 0, then you don't need to add any red).