1

Say I have 1 red ball, 1 blue ball, 2 yellow balls, and 3 green balls, for a total of 7 balls.

I want to select 3 balls from the group of seven. How many ways can I do this?

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)

nbrooks
  • 18,126
  • 5
  • 54
  • 66
colinfang
  • 20,909
  • 19
  • 90
  • 173

2 Answers2

2

On second though, I suggest a generating function approach.

  • 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)

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:

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;

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.

PengOne
  • 48,188
  • 17
  • 130
  • 149
1
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).

Patrick87
  • 27,682
  • 3
  • 38
  • 73