computing the number of combinations

This is a discussion on computing the number of combinations within the C Programming forums, part of the General Programming Boards category; 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) ... ...

  1. #16
    Registered User pinko_liberal's Avatar
    Join Date
    Oct 2001
    Posts
    284
    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)
    The one who says it cannot be done should never interrupt the one who is doing it.

  2. #17
    Registered User
    Join Date
    Sep 2003
    Posts
    10
    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.
    Last edited by clover; 06-05-2004 at 01:50 AM.

  3. #18
    Registered User pinko_liberal's Avatar
    Join Date
    Oct 2001
    Posts
    284
    Quote 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
    Last edited by pinko_liberal; 06-05-2004 at 01:50 AM.
    The one who says it cannot be done should never interrupt the one who is doing it.

  4. #19
    Registered User pinko_liberal's Avatar
    Join Date
    Oct 2001
    Posts
    284
    Quote 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.
    The one who says it cannot be done should never interrupt the one who is doing it.

  5. #20
    Registered User
    Join Date
    Sep 2003
    Posts
    10
    for n=14 r=11

  6. #21
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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().

  7. #22
    Registered User pinko_liberal's Avatar
    Join Date
    Oct 2001
    Posts
    284
    Quote Originally Posted by clover
    for n=14 r=11
    I am getting 364 which is the correct answer.
    The one who says it cannot be done should never interrupt the one who is doing it.

  8. #23
    Registered User pinko_liberal's Avatar
    Join Date
    Oct 2001
    Posts
    284
    Quote 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.
    Last edited by pinko_liberal; 06-05-2004 at 02:46 AM.
    The one who says it cannot be done should never interrupt the one who is doing it.

  9. #24
    Registered User pinko_liberal's Avatar
    Join Date
    Oct 2001
    Posts
    284
    I corrected the code above a bit
    The one who says it cannot be done should never interrupt the one who is doing it.

  10. #25
    Registered User pinko_liberal's Avatar
    Join Date
    Oct 2001
    Posts
    284
    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
    Last edited by pinko_liberal; 06-05-2004 at 10:52 AM.
    The one who says it cannot be done should never interrupt the one who is doing it.

  11. #26
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    And that is why I choose to use the reduction method instead. Slower yes, more memory yes, larger range of accurate numbers yes.

  12. #27
    Registered User pinko_liberal's Avatar
    Join Date
    Oct 2001
    Posts
    284
    Thantos,
    What is the smallest value of C(2n,n) for which your method fails?
    Last edited by pinko_liberal; 06-05-2004 at 10:53 AM.
    The one who says it cannot be done should never interrupt the one who is doing it.

  13. #28
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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

  14. #29
    Registered User pinko_liberal's Avatar
    Join Date
    Oct 2001
    Posts
    284
    Quote 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!!!
    The one who says it cannot be done should never interrupt the one who is doing it.

  15. #30
    Registered User pinko_liberal's Avatar
    Join Date
    Oct 2001
    Posts
    284
    Quote 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
    The one who says it cannot be done should never interrupt the one who is doing it.

Page 2 of 3 FirstFirst 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with this compiler error
    By Evangeline in forum C Programming
    Replies: 7
    Last Post: 04-05-2008, 10:27 AM
  2. Finding a number within a number
    By jeev2005 in forum C Programming
    Replies: 2
    Last Post: 01-10-2006, 08:57 PM
  3. Prime number program problem
    By Guti14 in forum C Programming
    Replies: 11
    Last Post: 08-06-2004, 05:25 AM
  4. parsing a number
    By juancardenas in forum C Programming
    Replies: 1
    Last Post: 02-19-2003, 01:10 PM
  5. Random Number problem in number guessing game...
    By -leech- in forum Windows Programming
    Replies: 8
    Last Post: 01-15-2002, 05:00 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21