combination function in c++?

Question

i want function that calculates combination of n and r. is there something in math.h library.
nCr=n!/((n-r)!r!)

Answer 1

No, the C++ standard library does not have that.



The classic overflow-minimizing algorithm from Knuth is



uint64_t Combinations(unsigned int n, unsigned int k)

{

     if (k > n)

         return 0;

     uint64_t r = 1;

     for (unsigned int d = 1; d <= k; ++d)

     {

         r *= n--;

         r /= d;

     }

     return r;

}



(source: http://stackoverflow.com/questions/1838368/calculating-the-amount-of-combinations )



If you're worried about performance due to recalculating these numbers a lot, see if you're recalculating the same numbers over and over, in which case you can memoize or otherwise tabulate the results.

Answer 2

If the string length is not known in advance, the only way to do this is through a recursive function. Since you can't use functions, you can write a program to write all combinations of a 1, 2, 3, 4 and 5 character long strings. It will be something like this: char str[5]; scanf( "%d", str ); switch( len(string) ) : case 1: printf( "%d", str ); break; case 2: // str is 2 characters long int i, j; for( i = 0; i < 2; i++ ) printf( "%d", str[i] ); for( j = 0; j < 2; j++ ) if( j != i ) { printf( %d \n", str[ j ] ); } case 3: // str is 3 characters long int i, j, k; and so on...

Answer 3

You may need to write your own factorial function (it isn't hard), or just copy paste what I wrote below



long Factorial(long val)

{

long Result = 1;

for(long i = 2; i < val; ++i)

{

Result *= i;

}

return Result

}



As for the combination function



long Combination(long N, long R)

{

return (Factorial(N) / ((Factorial(N-R) * Factorial(R));

}



should work.