-4

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.

rmaddy
  • 314,917
  • 42
  • 532
  • 579
Henrik Maaland
  • 210
  • 2
  • 14

1 Answers1

0

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".
 ***************************************************************************/
John Forkosh
  • 502
  • 4
  • 14