# Write a C function called combinations which takes n and r as inputs, and returns the number of combinations

The number of ways of selecting r objects from n possible choices not in any particular order is called the combinations, and is defined by n!/((n-r)!r!) For example, the number of ways of selecting 3 objects from 20 is 20! / (17!x3!) = 20x19x18 / 3x2x1 = 1140. Write a C function called combinations which takes n and r as inputs, and returns the number of combinations.

Am I misunderstanding if I am thinking that a function with two inputs would be:

``````int combinations(int n, int r)
{
//solving combinations here

//return combination
}

``````

I am actually not able to figure out how to resolve this question with two inputs in the function, any help would be appreciated.

The real problem, of course, is that you can't just calculate n! and r! separately because the factorial function grows so rapidly ( even people who say "exponentially" without knowing what they're talking about would underestimate it :). Instead, you want to combine the multiplications and divisions in such a way that permits you to evaluate the overall quotient without intermediate overflow, for as-large-as-possible n,r arguments.

So the algorithm's the real question. The coding's pretty trivial. For my purposes I needed binomial weights, i.e., (n,r)/2^n. So my comment block describing my algorithm is reproduced below, but none of the code, which I'll leave to you. Also, my algorithm takes advantage of all those additional 2-factors, which you can't do. So what I'm giving you below is just a clue how you might want to proceed...

``````/****************************************************************************
* Function:    bweight ( n, i )
* Purpose:     Calculate [binomial coefficient]/2**n = [n!/(i!(n-i)!)]/2**n.
* --------------------------------------------------------------------------
* Arguments:   n (I)           n items...
*              i (I)           ...taken i at a time
* Returns:     (double)        as above, or 0 for any argument error
* --------------------------------------------------------------------------
* Notes:     o Algorithm prevents dividing one (very) large number
*              by another.  Note that
*              n!/(i!(n-i)!) = (n-i+1)(n-i+2)...(n-i+i)/1*2*...*i if i<=n-i,
*                      or    = (i+1)(i+2)...(i+(n-i))/1*2*...*(n-i) if i>n-i
*              In both cases the number of terms is the same in the
*              numerator and denominator, and in both cases it's <=n/2.
*              Thus, we divide each term by 4=2*2 as we accumulate the
*              terms.  At the end, we divide by any remaining powers of two
*              necessary to achieve the total 2**n factor required.  This
*              helps prevent the numerator from getting too large before
*              the denominator "cathces up".
***************************************************************************/
``````