better way to work with combinatorics?

[zacklucky]

I'm using the unsigned long long data type while doing a combinatorics problem that is basically you have x urns and y colors and you want at least one of each color. But I noticed around the mark where you have ~20 urns long long starts to fail me. Should I be trying to do some recursion/memoziation as a way to keep the #s smaller?

  /*
 Rohit dreams he is in a shop with an infinite amount of marbles. He is allowed
 to select n marbles. There are marbles of k different colors. From each color
 there are also infinitely many marbles. Rohit wants to have at least one marble
 of each color, but still there are a lot of possibilities for his 
selection. In his effort to make a decision he wakes up. Now he asks you how 
many possibilities for his selection he would have had. Assume that marbles of 
equal color can't be distinguished, and the order of the marbles is irrelevant.
 */
// If we are selecting an r-combination from n elements with repetition, there are Choose(n+r−1,r)

//marbles kept less than 20

#include <iostream>
#include <vector>

int main(int argc, const char * argv[]) {
    unsigned long long int colors, marbles, sum1(1), sum2(1), sum3(1);
    std::cout << "How many marbles are there: ";
    std::cin >> marbles;
    std::cout << "How many colors are there: ";
    std::cin >> colors;
    if (colors > marbles)
    {
        std::cout << "There is no way to have at least one marble of each color\n";
    }
    else if (colors == marbles)
    {
        std::cout << "There is 1 way to select that\n";
    }
    else
    {
        for(unsigned long long int i = (marbles - 1); i > 0; i--)
        {
            sum1 *= i;
        }
            for(unsigned long long int j = (marbles - 1 - colors); j > 0; j--)
            {
                sum2 *= j;
            }
                for (unsigned long long int k = colors; k > 0; k--)
                {
                    sum3 *=k;
                }
        sum3 = sum2 * sum3;
        std::cout << "There are " << sum1/sum3 << " ways to select that\n";
    }
    
    
    return 0;
}

[Duthomhas]

This is a discrete math problem, that is stated confusingly. JSYK, r and k mean the same thing. I'll use k. The problem states that Rohit can choose k marbles from n different marble colors.

Before going further, I recommend a typedef for your number type, just to make reading things easier. (And an unsigned long long should be plenty large for what you wish to do.)

typedef unsigned long long int number;

The n-choose-k function is called the binomial coefficient, and is typically a difficult problem in computers. However, you have a convenient restriction: n,k <= 20. For that, you can get away with a simple brute force implementation. First, remember your math:

              n!
    (ⁿ_k) = ────────
           k!(n-k)!

Notice that the factorial function is in there a lot. You might as well write yourself a function to compute the factorial:

number factorial( number n )
{
    // todo. You'll need one loop.
}

Once you have that function, you can write your choose() function very easily:

number choose( number n, number k )
{
    // todo. You don't need a loop.
}

(These two functions are the crux of your homework, and you should try to fill them out yourself.)

Once you have that, what remains basically writes itself: get two numbers from the user, compute the answer, and print it. Remember, the solution was given to you:

  number possibilities = choose( n+k-1, k );

Hope this helps.

[zacklucky]

So the way i solved the problem was that since you're required to have one colored ball of each that the choose function is actually choose (n-1, k-1). For example 5 choose 3, you have 6 choices in the two that aren't taken AA BB CC AB AC BC. Which does correspond to 4 choose 2. Also tried 30 choose 7 and according to the test output 29 choose 6 does give the right answer. Pretty confusing. I did have to modify my loops. The n,k < 20 was just an arbitrary thing I noticed I would love if it could go bigger. Because I thought around 20 factorial was the limit for long long at 18 digits. Also quick question about typedef is there a specific coding style to use for the type names or is it just like variables? Thanks for the help this problem confused the hell out of me.

for(unsigned long long int i = (marbles - 1); i > 0; i--)
        {
            sum1 *= i;
        }
            for(unsigned long long int j = (marbles - colors); j > 0; j--)
            {
                sum2 *= j;
            }
                for (unsigned long long int k = colors - 1; k > 0; k--)
                {
                    sum3 *=k;
                }
        std::cout << "There are " << sum1/sum3 << " ways to select that\n";
    }

[Duthomhas]

Er, no, your math is off.

You have (I hope) realized that the assignment expects you to consider two scenarios:

1) Rohit may choose fewer or equal marbles than there are colors: k ≤ n;
2) Rohit may choose more marbles than there are colors: k > n.

In the first case, you must choose without repetition (since Rohit wants one of each color -- his hard choice is which colors he might have to go without):

    choose( n, k ) 

In the second case, you must think harder. You have it right that your first n marbles are not a choice (since Rohit wants one of each color). That leaves k-n marbles to be chosen from n marbles, with repetition.

Remember that formula your professor gave you?

    choose( n+k-1, k ) 

That's if you are choosing k items with repetition. But you aren't choosing k items, you are choosing (k-n) items. With a little mathematical substitution (replace k with k-n) it becomes:

    choose( k-1, k-n )

If you like, look at it with an example:

given n=5 and k=7, the first n choices are, of course, (1,2,3,4,5). That leaves us with k-n=2 spaces to fill with n=5 different colors in any combination we wish:

1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5
15 possibilities

The correct answer is 15.

Here are a few other examples:

n=4            n=2
k=9            k=7
1 1 1 1 1      1 1 1 1 1
1 1 1 1 2      1 1 1 1 2
1 1 1 1 3      1 1 1 2 2
1 1 1 1 4      1 1 2 2 2
1 1 1 2 2      1 2 2 2 2
1 1 1 2 3      2 2 2 2 2
1 1 1 2 4      6 possibilities
1 1 1 3 3
1 1 1 3 4      n=8
1 1 1 4 4      k=10
1 1 2 2 2      1 1
1 1 2 2 3      1 2
1 1 2 2 4      1 3
1 1 2 3 3      1 4
1 1 2 3 4      1 5
1 1 2 4 4      1 6
1 1 3 3 3      1 7
1 1 3 3 4      1 8
1 1 3 4 4      2 2
1 1 4 4 4      2 3
1 2 2 2 2      2 4
1 2 2 2 3      2 5
1 2 2 2 4      2 6
1 2 2 3 3      2 7
1 2 2 3 4      2 8
1 2 2 4 4      3 3
1 2 3 3 3      3 4
1 2 3 3 4      3 5
1 2 3 4 4      3 6
1 2 4 4 4      3 7
1 3 3 3 3      3 8
1 3 3 3 4      4 4
1 3 3 4 4      4 5
1 3 4 4 4      4 6
1 4 4 4 4      4 7
2 2 2 2 2      4 8
2 2 2 2 3      5 5
2 2 2 2 4      5 6
2 2 2 3 3      5 7
2 2 2 3 4      5 8
2 2 2 4 4      6 6
2 2 3 3 3      6 7
2 2 3 3 4      6 8
2 2 3 4 4      7 7
2 2 4 4 4      7 8
2 3 3 3 3      8 8
2 3 3 3 4      36 possibilities
2 3 3 4 4
2 3 4 4 4
2 4 4 4 4
3 3 3 3 3
3 3 3 3 4
3 3 3 4 4
3 3 4 4 4
3 4 4 4 4
4 4 4 4 4
56 possibilities

Hope this helps.

[zacklucky]

It's not an actual assignment. I decided to make it that if there aren't enough colors then the program says it's impossible. I agree with your math but i get the same answers using k-1, n-1. It's because they are equivalent I assume?

k=7, n=5 choose(6,4) =15
k=9, n=4 choose(8,3) =56
k=7, n=2 choose(6,1) =6
k=10 n=8 choose(9,7) =36

whereas you do n-1, n-k

k=7, n=5 choose(6,2) =15
k=9, n=4 choose(8,5) =56
k=7, n=2 choose(6,5) =6
k=10 n=8 choose(9,2) =36

[Duthomhas]

Oop! Yep. They are the same.