Combination(N choose R) ?

Code:

---

#include <stdio.h>
#include "Boolean.h"
#include "combinatorics.h"

/* For all the functions below, return TRUE if the
  calculation is successful, FALSE if overflow occurs
  Return the calculated value in the pass by reference
  parameter provided
*/

Boolean calcFactorial (int n, int* nfact)
{
    *nfact = 1;

        while(n > 0)
        {
              *nfact = *nfact * n;
                  n--;         
        }

        if(*nfact < 0x7fffffff)
        {
                return TRUE;
        }
        else
        {
                return FALSE;
        }
}

/*
Combination means C(n,r) = n!/( r! * (n-r)! )
where C(n,r) is the number of r-element subsets of an n-element set.
Better formula derived from above is:
          n ( n-1 ) ( n-2 ) ... ( n-r+1 )
 C(n,r) = -------------------------------
          r ( r-1 ) ( r-2 ) ... (3)(2)(1)


  Return True if calculation is successful. False if
  Overflow occurs.
*/

Boolean calcCNR( int n, int r, int* cnr )
{
                      //#define min(n,r) = (((n) < (r)) ? (n) : (r));

    int answer = *cnr;
        int multiplier;
        int divisor = 1;
        int k;

        if(n < r)
        {
                k = n;
        }
        else
        {
                k = r;
        }

        while(divisor <= k)
        {
                        answer = (answer * multiplier) / divisor;
       
                    multiplier--;
                    divisor++;
        }
}

---

Quote:

---

The Algorithm For N-Choose-R in High Level Pseudocode:

Let k = min (r, n-r)
Start answer = 1
Start multiplier = n
Start divisor = 1
while divisor<= k do
{ answer = ( answer * multiplier ) div divisor # this will evenly divide
decrement the multiplier
increment the divisor
}

---

Here is my program so far. I need help on calcCNR(n choose r) function. I'm not worried about detecting overflow yet. Need to get it to calculate correctly first. But it's returning garbage so far. The algorithm is given above. The most confusing part for me is "let k = min (r, n-r). I have attempted to code that, but not sure if it's correct. Help needed.

You're doing it the wrong way. Do a search on the internet for "Binomial Coefficients" and "Dynamic Programming". I just wrote this program a few weeks ago in C++, and you will be surprised, you don't use the formula n!/(k! * (n-k)!).

As the matter of fact, this was the pseudo-code that I found, and I converted it to c++. The article explains the algorithm pretty well:

http://www.csc.liv.ac.uk/~ped/teacha...or/dyprog.html

The problem is that, i have to use the given function param and algorithm as my professor wants it :mad:

> I need help on calcCNR(n choose r) function.
Why isn't it calling your factorial function with 3 different values then.

Or follow your pseudo-code properly
int answer = *cnr;
Is NOT
Start answer = 1

You start with
int answer = 1;

And you finish with
*cnr = answer;

Code:

---

/*
Combination means C(n,r) = n!/( r! * (n-r)! )
where C(n,r) is the number of r-element subsets of an n-element set.
Better formula derived from above is:
          n ( n-1 ) ( n-2 ) ... ( n-r+1 )
 C(n,r) = -------------------------------
          r ( r-1 ) ( r-2 ) ... (3)(2)(1)


  Return True if calculation is successful. False if
  Overflow occurs.
*/

Boolean calcCNR( int n, int r, int* cnr )
{
    #define min(n,r)  (((n) < (r)) ? (n) : (r));

   
        int answer = 1;
        int multiplier = n;
        int divisor = 1;
        int k;
       

        k = min(r,n-r);
   
       
        while(divisor <= k)
        {
                        answer = ((answer * multiplier) / divisor);
                        *cnr = answer;

                    multiplier--;
                    divisor++;                       
        }
        return TRUE;
}

---

Quote:

---

C(10,3) = 120
C(10,7) = 120
C(18,13) = 8568
C(21,12) = 293930
C(10,1) = 10
C(10,10) = 1 (mine returns garbage for this one)??
C(10,0) = 1 (mine returns garbage for this one)??

---

the numbers above i tested worked so far, but when i get to 10C10 or 10C0, it returns garbage when it's suppose to be 1.
Somebody see anything wrong? The algorithm is in the first post.

So put some printf statements in (or use the debugger to single-step the code) and figure out whether it's the code (or your algorithm) which is broken.

Code:

---

Boolean calcCNR(int n, int r, int *cnr)
{
#define min(n,r)  (((n) < (r)) ? (n) : (r));
    int answer = 1;
    int multiplier = n;
    int divisor = 1;
    int k;

    k = min(r, n - r);
    printf("n=%d, r=%d, k=%d\n", n, r, k);

    while (divisor <= k) {
        answer = ((answer * multiplier) / divisor);
        *cnr = answer;
        printf("Intermediate answer=%d\n", answer);
        multiplier--;
        divisor++;
    }
    return TRUE;
}

---