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.

1 answer

  • answered 2019-10-08 04:37 John Forkosh

    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".