N Choose R

**.ZG.** · 05-17-2004

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.

**quzah** · 05-17-2004

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.

**Thantos** · 05-17-2004

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)  );

**Thantos** · 05-17-2004

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.

**DavT** · 05-17-2004

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

**quzah** · 05-17-2004

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]

**.ZG.** · 05-17-2004

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.

**DavT** · 05-18-2004

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...

Thread: N Choose R

Thread Tools

Search Thread

Display

N Choose R

Similar Threads

HELP!!!!emergency Problem~expert please help

HELP!!!!emergency ~expert please help

Help me choose my hardware

Probablity algorithm for N choose M in C or C++

When would you choose to return an error code rather than throw an exception?