Thread: computing the number of combinations

Essentially what I have tried to do in the above code is to calculate
1=C(n-r,0) => C(n-r+1,1) => C(n-r+2,2) ... => C(n-r + r,r)=C(n,r)
by using the iterative formula
C(n+1,r+1)=( (n+1)*C(n,r))/(r+1)

I tried it pinko but it does not work. I found my mistake in the code. I should use double as a data type not int.

Originally Posted by clover

I tried it pinko but it does not work

For what input?
It works for me fine.
Give me an n and a r for which it does not work.

My output for n=30
choose1(30,0)=1
choose1(30,1)=30
choose1(30,2)=435
choose1(30,3)=4060
choose1(30,4)=27405
choose1(30,5)=142506
choose1(30,6)=593775
choose1(30,7)=2035800
choose1(30,8)=5852925
choose1(30,9)=14307150
choose1(30,10)=30045015
choose1(30,11)=54627300
choose1(30,12)=86493225
choose1(30,13)=119759850
choose1(30,14)=145422675
choose1(30,15)=155117520
choose1(30,16)=145422675
choose1(30,17)=119759850
choose1(30,18)=86493225
choose1(30,19)=54627300
choose1(30,20)=30045015
choose1(30,21)=14307150
choose1(30,22)=5852925
choose1(30,23)=2035800
choose1(30,24)=593775
choose1(30,25)=142506
choose1(30,26)=27405
choose1(30,27)=4060
choose1(30,28)=435
choose1(30,29)=30
choose1(30,30)=1

Originally Posted by clover

I tried it pinko but it does not work. I found my mistake in the code. I should use double as a data type not int.

Show me your code.

Originally Posted by clover

for n=14 r=11

I am getting 364 which is the correct answer.

Originally Posted by Thantos

31 C 15 : For function choose1() results were 14209041 correct value is 300540195. The values from that depth on breaks down. Same results for function choose().

That is an over flow, error, 31 is hitting the bar using this method.
Still if you want to push the bar further accumulate products in higher precision.

Code:

#include <stdio.h>

unsigned long long
choose1(unsigned long n, unsigned long r) /*non recursive version*/
{
    unsigned long 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("choose1(%lu,%lu)=%llu\n",n,i,choose1(n,i));
   } 
   return 0;
}

choose1(31,15) is 300540195 as you want.
But you will of course find sufficiently large values of n for which this will break.

I corrected the code above a bit

The above code will work for C(n,r) iff
n*C(n-1,r-1) < 2**32-1
[added later]
It should ULLONG_MAX above, or 2**64-1

Thantos,
What is the smallest value of C(2n,n) for which your method fails?

Originally Posted by Thantos

It fails at n 35 r 15 is the first failing point. n 36 r 18 is the 2n, n failing point.
Using the long long int format the 2n,n failing point appears to be 70,35

For my code its (64,32) so you are squeezing five more bionomial sequences.
Not bad!!! Good work!!!

Originally Posted by Thantos

It fails at n 35 r 15 is the first failing point. n 36 r 18 is the 2n, n failing point.
Using the long long int format the 2n,n failing point appears to be 70,35

Dude, what is the sizeof(unsigned long long) on your system,
C(70,35)= 112186277816662845432
ULLONG_MAX= 18446744073709551615 (on my system)
C(70,35) > ULLONG_MAX