Combinations(N choose R) ?

[koolguysj]

#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++;
	}
}

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.

[aj.wh.ca]

Yes , The problem is in your implementation of min function. In fact the #define which you have commented is correct.
Uncomment the #define and then instead of

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

write k = min(r,n-r) ;

Do you need to take care of cases like C(5,11) ? The above may not work then. Will need to change the condition.

[koolguysj]

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;
	}
	*/

	k = min(r,n-r);
    answer = 1;
	while(divisor <= k)
	{
		    

			answer = (answer * multiplier) / divisor;
	
		    multiplier--;
		    divisor++;
	}
}


void main()
{
   int result;
	int n;
	int r;

	printf("Input two number:  ");
	scanf("%d %d", &n, &r);

	calcCNR(n, r, &result);

	printf("result of cnr is: %d\n", result);
}

Not working yet. Help please.

[murschech]

One problem is that you'r not correctly initializing the variables in calcCNR. The last variable is where the result appears. When you call the function this variable has no significant value. I'm surprised that the compiler let you get away with the statement
"anwer = *cnr". The initial value of answer should be "answer = 1". At the end you should set *cnr = answer.

Come to think of it, why are you using indirection at all? Why not just have the function calcCNR return the value you've computed?