Combination(N choose R) ?

This is a discussion on Combination(N choose R) ? within the C Programming forums, part of the General Programming Boards category; Code: #include <stdio.h> #include "Boolean.h" #include "combinatorics.h" /* For all the functions below, return TRUE if the calculation is successful, ...

  1. #1
    Registered User
    Join Date
    Mar 2005
    Posts
    14

    Combination(N choose R) ?

    Code:
    #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.

  2. #2
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    You're doing it the wrong way. Do a search on the internet for "Binomial Coefficients" and "Dynamic Programming". I just wrote this program a few weeks ago in C++, and you will be surprised, you don't use the formula n!/(k! * (n-k)!).
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  3. #3
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    As the matter of fact, this was the pseudo-code that I found, and I converted it to c++. The article explains the algorithm pretty well:

    http://www.csc.liv.ac.uk/~ped/teacha...or/dyprog.html
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  4. #4
    Registered User
    Join Date
    Mar 2005
    Posts
    14
    The problem is that, i have to use the given function param and algorithm as my professor wants it

  5. #5
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,485
    > I need help on calcCNR(n choose r) function.
    Why isn't it calling your factorial function with 3 different values then.

    Or follow your pseudo-code properly
    int answer = *cnr;
    Is NOT
    Start answer = 1

    You start with
    int answer = 1;

    And you finish with
    *cnr = answer;
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  6. #6
    Registered User
    Join Date
    Mar 2005
    Posts
    14
    Code:
    /*
    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 = 1;
    	int multiplier = n;
    	int divisor = 1;
    	int k;
    	
    
    	k = min(r,n-r);
        
    	
    	while(divisor <= k)
    	{
    			answer = ((answer * multiplier) / divisor);
    			*cnr = answer;
    
    		    multiplier--;
    		    divisor++;			
    	}
    	return TRUE;
    }
    C(10,3) = 120
    C(10,7) = 120
    C(18,13) = 8568
    C(21,12) = 293930
    C(10,1) = 10
    C(10,10) = 1 (mine returns garbage for this one)??
    C(10,0) = 1 (mine returns garbage for this one)??
    the numbers above i tested worked so far, but when i get to 10C10 or 10C0, it returns garbage when it's suppose to be 1.
    Somebody see anything wrong? The algorithm is in the first post.

  7. #7
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,485
    So put some printf statements in (or use the debugger to single-step the code) and figure out whether it's the code (or your algorithm) which is broken.

    Code:
    Boolean calcCNR(int n, int r, int *cnr)
    {
    #define min(n,r)  (((n) < (r)) ? (n) : (r));
        int answer = 1;
        int multiplier = n;
        int divisor = 1;
        int k;
    
        k = min(r, n - r);
        printf("n=%d, r=%d, k=%d\n", n, r, k);
    
        while (divisor <= k) {
            answer = ((answer * multiplier) / divisor);
            *cnr = answer;
            printf("Intermediate answer=%d\n", answer);
            multiplier--;
            divisor++;
        }
        return TRUE;
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. HELP!!!!emergency Problem~expert please help
    By unknowppl in forum C++ Programming
    Replies: 9
    Last Post: 08-21-2008, 06:41 PM
  2. HELP!!!!emergency ~expert please help
    By unknowppl in forum C Programming
    Replies: 1
    Last Post: 08-19-2008, 07:35 AM
  3. Help me choose my hardware
    By Mario F. in forum A Brief History of Cprogramming.com
    Replies: 28
    Last Post: 06-02-2008, 06:04 PM
  4. Probablity algorithm for N choose M in C or C++
    By kappajacko in forum C++ Programming
    Replies: 2
    Last Post: 09-20-2007, 04:19 PM
  5. N Choose R
    By .ZG. in forum C Programming
    Replies: 7
    Last Post: 05-18-2004, 02:43 AM

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