# Thread: computing the number of combinations

1. ## computing the number of combinations

what is wrong with the code it computes the result false

Code:
/* computes the number of combinations of n items taken r at a time by the formula
c(n,r)= n! / (r!(n-r)!), functions used are unsigned int no_of_combinations(unsiged int,
unsigend int) and unsigned int factorial ( unsigned int) */
#include<stdio.h>
void main()
{
/* function declarations */
unsigned int no_of_combinations( unsigned int, unsigned int);
/* variable declaration */
unsigned x,y,z;
char right_no = 'a';
/* function body */
while ( right_no == 'a' )
{
printf("\nEnter a number for the total number of items: ");
scanf("%d",&x);
printf("Enter the number of groups taken at a time: ");
scanf("%d",&y);
if ( y<=x )
{
z = no_of_combinations(x,y);
right_no = 'b';
}
/* end if */
}
/* end while */
printf("The number of combinations of %d taken %d at time is %d",x,y,z);
}
/* end function main */

/* function int factorial(int) */
unsigned int factorial(
/* input */  unsigned int num )
{
/* variable declarations */
unsigned int fact = 1;
unsigned int count = 2;
while ( count <= num )
{
fact = fact * count;
count++;
}
/* end while */
return fact;
}
/* end function int factorial(int) */

unsigned int no_of_combinations(
/* input */  unsigned int x,  unsigned int y )
{
/* variable declaration */
unsigned int ans, fact_of_n_minus_r;
unsigned int fact_of_n, fact_of_r;
/* function declaration */
unsigned int factorial( unsigned int);
/* function body */
fact_of_n = factorial(x);
fact_of_r = factorial(y);
fact_of_n_minus_r = factorial(x-y);
ans = fact_of_n / (fact_of_r * fact_of_n_minus_r);
return ans;
}
/* end function no_of_combinations */

2. void main()
that's int main(void)

void main()
{
/* function declarations */
unsigned int no_of_combinations( unsigned int, unsigned int);
you can't have function prototypes inside other functions

Your code is not effective, using that formula is not good because even unsigned ints can't hold a factorial of 14 or more. I would suggest using Pascal's triangle to find the number of combinations

3. here's a recursive implementation:
Code:
#include <stdio.h>

int pscl (int n, int k);

int main (void)
{
int n,k;
long int out;

printf("N choose K\n");

printf("Enter n:");
fflush(stdout);
scanf("%d", &n);

printf("Enter k:");
fflush(stdout);
scanf("%d", &k);

if (k > n)
{
printf("error, K must be <= N;\n");
return 1;
}

out = pscl(n, k);

printf("Number of Combinations is: %ld\n", out);

return 0;
}

int pscl (int n, int k)
{
if (k == 0)
return 1;
if (k == n)
return 1;

return pscl(n-1, k) + pscl(n-1, k-1);
}

4. Originally Posted by viaxd
that's int main(void)
you can't have function prototypes inside other functions

Your code is not effective, using that formula is not good because even unsigned ints can't hold a factorial of 14 or more. I would suggest using Pascal's triangle to find the number of combinations
Yes you can.

Quzah.

5. Originally Posted by viaxd
that's int main(void)

you can't have function prototypes inside other functions

Your code is not effective, using that formula is not good because even unsigned ints can't hold a factorial of 14 or more. I would suggest using Pascal's triangle to find the number of combinations
what is the pascal triangle?

6. Originally Posted by clover
what is the pascal triangle?
*sigh*

Quzah.

7. Originally Posted by viaxd
I would suggest using Pascal's triangle to find the number of combinations
The nCr method is using Pascal's triangle. Its how you find the coeffiecents without recursion.

I'm feeling really nice and since all it takes it diving into my folder of misc source code here is a nCr function I was working on.

Code:
int nCr2 (int n, int r)
{
int numnums = n - (n - r), count, count2;
int total=1;
int *nums;
int *dems;

if ( r == 0 && n != 0)
return 1;

if ( n == 0 || n < r)
return 0;

dems =  malloc (sizeof(int) * r);
nums = malloc (sizeof(int) * numnums );

if ( !nums || !dems )
return 0;

for (count=0; count < numnums; count++)
nums[count] = n - count;

for (count=0; count < r; count++)
dems[count] = r - count;

for (count=0; count < numnums; count++)
for ( count2=0; count2 < r; count2++)
checkfact( nums+count, dems+count2);

for (count=0; count< numnums; count++)
total *= nums[count];

for (count=0; count < r; count++)
total /= dems[count];

free(nums);
free(dems);

}
guess you'll need this one also
Code:
void checkfact (int *n, int *d)
{
if ( *d == 1)
return;
if ( *n % *d == 0 )
{
*n = *n / *d;
*d = 1;
}
}
Now of course to make it harder I removed all the comments (evil grin)

Though the basic process is simple.
1) Make sure we can't short circuit the operation
2) Make enough room for the numeritor and denomitor
3) Go through one by one and see if we can reduce.
- Note: Through expermenting I found that the denomitor will always reduce to 1
4) get the product of the remaining values
5) free the space
6) return the value

Edit: Had to undo a change I made during the copy and paste.
Also a return of 0 from nCr indicates an error in the numbers passed to it

Edit #2: Thank viaxd. The error was not so much in the copying but with a simple logic that didn't manifest itself until I took out the divison of the remaining denomitors which should have been needed because they were suppose to all reduce to one.

8. I'm feeling really nice and since all it takes it diving into my folder of misc source code here is a nCr function I was working on.
It's broken. I've tested your function with different n and r and the output is incorrect.

Code:
n = 5
r = 4
should be = 5

9. Gah I must have copied something wrong. My version here gives 5. Let me take a look and I'll edit the code.

Edit: Change made and explained at the bottom of the post.

10. hmm, it is still wrong for some n and r, like
n = 21, r = 10, yours = 1410864, should be = 352716
n = 30, r = 26, yours = 109620, should be = 27405
n = 30, r = 20, yours = 1024470208, should be = 30045015
n = 30, r = 25, yours = 570024, should be = 142506

11. Grrr, I knew I should just have copied it how it was orginally. The code is edited and is a copy of what I have. There is an error with 30 C 20 but I believe that to be an overflow of int problem. I need to look at why the denomitor array isn't reducing all the values to 1.

Still using nCr is a better method than pascal's triangle because you will still have the same trouble with overflowing.

12. Man getting the denom to reduce down was a pain in the arse. Had to make a function to test for the lowest common denom.

From looking at the output the results seem to overflow at about 35 C 17 and 35 C 18. If anyone has access to a 64 bit system I'd like to see if it holds up. Actually I am pretty happy with the speed of it. Doing it from n 0 to n 50 with all possible r values for each it did it in about a second on an old computer.

Code:
void lcd (int *a, int *b)
{
int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};

int smallest = *a < *b ? *a : *b;
int count;

for (count=0; count<sizeof primes/sizeof primes[0] && primes[count] * primes[count] <= smallest; count++)
{
if ( *a % primes[count] == 0 && *b % primes[count] == 0 )
{
*a /= primes[count];
*b /= primes[count];
smallest = *a < *b ? *a : *b;
}
}
}

void checkfact (int *a, int *b)
{
int temp;
if ( *a == 1)
return;
if ( *a % *b == 0 )
{
temp = *a;
*a = *a / *b;
*b = 1;
}
else
lcd (a, b);
}

unsigned int nCr2 (int n, int r)
{
int numnums = n - (n - r), count, count2;
unsigned int total=1;
int *nums;
int *dems;
int repeat = 0;

if ( r == 0 && n != 0 )
return 1;

if ( n == 0 || n < r)
return 0;

dems =  malloc (sizeof(int) * r);
nums = malloc (sizeof(int) * numnums );

if ( !nums || !dems )
return 0;

for (count=0; count < numnums; count++)
{
nums[count] = n - count;
}

for (count=0; count < r; count++)
{
dems[count] = r - count;
}

do
{
repeat = 0;
for (count=0; count < numnums; count++)
for ( count2=0; count2 < r; count2++)
checkfact( nums+count, dems+count2);

for (count=0; count < r; count++)
for ( count2=0; count2 < numnums; count2++)
checkfact( dems+count, nums+count2);

for (count=0; count < r; count++)
if ( dems[count] != 1 )
{
repeat = 1;
break;
}

}while(repeat);

for (count=0; count< numnums; count++)
total *= nums[count];

free(nums);
free(dems);

}

13. Can someone please check this code.
Unless the result of C(n,r) is too large to hold in unsigned long it should give the right answer.
Code:
#include <stdio.h>

unsigned long
choose(unsigned long n, unsigned long r)
{
if( 2*r > n) r = n-r;/*c(n,r)=c(n,n-r)*/
if( (r<0) || (r>n) ) return 0;/*error*/
else if(r==0) return 1;
else if(r==1) return n;
return choose(n-1,r-1)+choose(n-1,r);
}

int
main(void)
{
unsigned long n,i;
printf("Give n\n");
scanf("%lu",&n);
printf("n=%lu\n",n);
for(i=0;i<=n;i++)
printf("choose(%lu,%lu)=%lu\n",n,i,choose(n,i));
return 0;
}

14. This seems to be a much faster recursive way of computing the bionomial coefficients
Code:
#include <stdio.h>

unsigned long
choose(unsigned long n, unsigned long r)
{
if( 2*r > n) r = n-r;/*c(n,r)=c(n,n-r)*/
if( (r<0) || (r>n) ) return 0;/*error*/
else if(r==0) return 1;
else if(r==1) return n;
else
{
unsigned long t;
t=choose(n-1,r-1);
return (n*t)/r;/*c(n,r)=(n*c(n-1,r-1))/r*/
}
}

int
main(void)
{
unsigned long n,i;
printf("Give n\n");
scanf("%lu",&n);
printf("n=%lu\n",n);
for(i=0;i<=n;i++)
printf("choose(%lu,%lu)=%lu\n",n,i,choose(n,i));
return 0;
}

15. ## the non recursive version

So, I got this non recursive version where you do not have to compute the factorials at all.
Code:
#include <stdio.h>

unsigned long
choose(unsigned long n, unsigned long r)/*recursive version*/
{
if( 2*r > n) r = n-r;/*c(n,r)=c(n,n-r)*/
if( (r<0) || (r>n) ) return 0;/*error*/
else if(r==0) return 1;
else if(r==1) return n;
else
{
unsigned long t;
t=choose(n-1,r-1);
return (n*t)/r;/*c(n,r)=(n*c(n-1,r-1))/r*/
}
}

unsigned long
choose1(unsigned long n, unsigned long r) /*non recursive version*/
{
unsigned long comb=1,num,den;
if( 2*r>n) r=n-r;
if( (r<0) || (r>n) ) return 0;/*error*/
for(num=n-r,den=0;num<n;num++,den++)
{
comb = ( (num+1)*comb )/(den+1);
}
return comb;
}

int
main(void)
{
unsigned long n,i;
printf("Give n\n");
scanf("%lu",&n);
printf("n=%lu\n",n);
for(i=0;i<=n;i++)
{
printf("choose(%lu,%lu)=%lu\n",n,i,choose(n,i));
printf("choose1(%lu,%lu)=%lu\n",n,i,choose1(n,i));
}
return 0;
}