N Choose R

This is a discussion on N Choose R within the C Programming forums, part of the General Programming Boards category; Im trying to calculate N Choose R by multiplication but it returns some crazy value like -1#inde. Its for a ...

  1. #1
    Registered User
    Join Date
    May 2004
    Posts
    5

    N Choose R

    Im trying to calculate N Choose R by multiplication but it returns some crazy value like -1#inde. Its for a prac. I have already done it iteratively and recursively, and need to do it by multiplication.

    The formula we were given was:

    N Choose R = (n / r) * ( (n - 1) / (n - 2) ) * ... ((n - r + 1) / 1).

    The code I have now is:

    Code:
    /*************************************
    CALCULATE N CHOOSE R BY MULTIPLICATION
    *************************************/
    
    float MultiplicationFactorial(float n, float r)
    {
    
    	float i = 0;
    	float output = 0; 
    	
    	if(r == 0)
    	{
    		
    		output = 1;
    		return output;
    
    	}
    
    	else
    	{
            
    		for(i = 0; (r - i) == 1; i++)
    		{
    			
    		output = (output * (( n + i) / (r + i)));
    		return output;
    
    		}
    
    	}
    
    }
    Any suggestions?

    the variables that im passing to the function are all floats. If I put n = 4 and r = 2, then it should return 6.

    Any help appreciated.

    .ZG.

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Well, you're putting a return statement inside your loop. In other words, it returns from the function on the very first loop iteration. I'm guessing that's now a GoodThingTM.

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

  3. #3
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Ack! nCr is so much simplier.

    n!/ ( (n-r)!r!)

    You shouldn't be passing floats, this is all integer math.

    Code:
    int getfactorial ( int n )
    {
      int total = 1;
      int count;
    
      if ( n == 0 )
        return total;
    
      for (; n > 0; n--)
        total *= n;
    
      return total;
    }
    Call as such:
    Code:
    int n = 4, r = 2;
    int nCr;
    nCr = getfactorial (n) / ( getfactorial(n-r) * getfactorial(r)  );
    Last edited by Thantos; 05-17-2004 at 06:08 AM. Reason: removed an unneeded (

  4. #4
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Well this is a slightly better way.
    since 10C4 would break down into:
    10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
    ----------------------------------------------
    6 * 5 * 4 * 3 * 2 * 1 * 4 * 3 * 2 * 1

    it can be reduced to:
    10 * 9 * 8 * 7
    ------------------
    4 * 3 * 2 * 1

    Which makes it less likely to overflow but it still will.

    Here is the new method:
    Code:
    int nCr (int n, int r)
    {
      int num=1, dem=1, count;
    
      if ( r == 0 )
        return 1;
    
      for (count=0; count< n - (n - r); count++)
        num *= (n - count);
    
      for (;r>1; r--)
        dem *= r;
    
      return num/dem;
    }
    Only way to keep it from overflowing is to go through the numbers to find ways to reduce it before you multiply.

  5. #5
    Registered User
    Join Date
    Mar 2003
    Posts
    143
    Looking through your original code there are three errors that stand out:
    Code:
    float output = 0;
    
    /* should be */
    
    float output = 1.0f;
    
    /* and */
    
    for(i = 0; (r - i) == 1; i++)
    {
      output = (output * (( n + i) / (r + i)));
      return output;
    }
    
    /* should be */
    
    for(i = 0; (r-i) >= 1; i++)
    {
      output = (output * (( n - i) / (r - i)));
      return output;
    }
    Also, I agree with quzah that you should really only have one return in the function,
    its a style thing but good consistent style tends to prevent errors.

    HTH
    DavT
    -----------------------------------------------

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by DavT
    Looking through your original code there are three errors that stand out:
    Code:
    /* should be */
    
    for(i = 0; (r-i) >= 1; i++)
    {
      output = (output * (( n - i) / (r - i)));
      return output;
    }
    Also, I agree with quzah that you should really only have one return in the function,
    its a style thing but good consistent style tends to prevent errors.

    HTH
    You still have the same problem they do. Walk through that loop, and you'll find there is no need for a loop at all the way you have it:
    Code:
    /* three lines */
    for(i = 0; (r-i) >= 1; i++)
    {
        output = (output * (( n - i) / (r - i)));
        return always right now no matter what the loop says
    }
    You may as well just write:
    Code:
    /* two lines */
    output = output * ((n - 0) / (r - 0));
    return output;
    Which can be simplified even more to just:
    Code:
    /* a single line */
    return output * ( n / r );
    Which is not what you want. That as my point.

    Quzah.
    [edit]/* comments added for clarification of my point */[/edit]
    Last edited by quzah; 05-17-2004 at 06:59 PM.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User
    Join Date
    May 2004
    Posts
    5
    Thanks for the help. I can't do it any other way than what I have in the previous code. I have to calculate the whole thing iteratively, then recursively (which works fine) and now using the formula. I fixed all the errors I can find, but it still isn't working.

    The code I have now is:

    Code:
    float MultiplicationFactorial( float n, float r)
    {
    
          float i = 0;
          float Output = 0;
    
          if(r == 0)
         {
    
                 Output = 1;
                 return Output;
    
         }
    
         else
         {
    
               for(i = 0; (r - i) > 0; i++)
               {
    
                       Output = ( Output * (( n - i) / (r - i)) );
    
               }
    
               return Output;
    
    
          }
    
    }
    I really cant see why it wont work. When I go through it in my head it works but not in the program.

    .ZG.

  8. #8
    Registered User
    Join Date
    Mar 2003
    Posts
    143
    Output should not be initialised to 0; 0*x = 0 everytime.
    I've checked my code now (thanks quzah!), if you fix
    that one thing it works...
    DavT
    -----------------------------------------------

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. Replies: 5
    Last Post: 06-06-2007, 11:10 PM

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