Thread: computing the number of combinations

  1. #1
    Registered User
    Join Date
    Sep 2003
    Posts
    10

    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 */
    Last edited by Salem; 06-03-2004 at 02:03 AM. Reason: Removed useless colour tags, added useful code tags

  2. #2
    ~viaxd() viaxd's Avatar
    Join Date
    Aug 2003
    Posts
    246
    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. #3
    ~viaxd() viaxd's Avatar
    Join Date
    Aug 2003
    Posts
    246
    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. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote 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.
    Hope is the first step on the road to disappointment.

  5. #5
    Registered User
    Join Date
    Sep 2003
    Posts
    10
    Quote 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. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by clover
    what is the pascal triangle?
    *sigh*

    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Quote 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);
    
      return total;
    }
    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.
    Last edited by Thantos; 06-04-2004 at 11:46 AM.

  8. #8
    ~viaxd() viaxd's Avatar
    Join Date
    Aug 2003
    Posts
    246
    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
    your result = 120
    should be = 5

  9. #9
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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.
    Last edited by Thantos; 06-04-2004 at 09:32 AM.

  10. #10
    ~viaxd() viaxd's Avatar
    Join Date
    Aug 2003
    Posts
    246
    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. #11
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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. #12
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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);
    
      return total;
    }

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

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

  15. #15
    Registered User pinko_liberal's Avatar
    Join Date
    Oct 2001
    Posts
    284

    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;
    }
    Last edited by pinko_liberal; 06-04-2004 at 11:31 PM.
    The one who says it cannot be done should never interrupt the one who is doing it.

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, 09: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, 04: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