Urgent Permutations Help Needed!

[JStinsch]

So I need lots of help, like step-by-step help pretty much. I have searched the entire forum for code and have tried out other peoples' code to give myself an idea of what I'm looking for and it seems that regardless of what I do I cannot get an idea to the following problem for my assignment:

The number of permutations of a set of n items taken r at a time is given by the following formula:
n!
-------
r!(n-r)!

Where n! is the factorial of n. if there are 12 people in your class and you want to divide the class into teams of 3 members, you can compute the number of different teams that can be arranged using this formula. Write a C++ program that determines the number of potential team assignments. you will need to use the double type for this computation. Be sure to use proper formatting and appropriate comments in your code. the outputs should be labeled clearly and formatted neatly.

I've paid attention in class and everything that has been taught has made sense to me but no matter what code I look up or try to use it just does not work or does not make sense. This is my first class of coding ever and prior to this assignment we have not used factorials nor permutations in coding for class so I'm simply at a loss.

The answer I believe I'm looking for (after entering in the formula mentioned in the beginning) is 220, but I can get nowhere near it. This is all that I really have which is declarations but I can't find or make a code that actually works so far:

double students = 12.0;
double teams;
double teamSize = 3.0;

While giving me the answer would help greatly, I'm trying to actually learn from this assignment as well, so helping me figure this out rather than giving me the answer would be appreciated more.

[keskiverto]

Use a loop to compute a factorial.

[JStinsch]

Okay I've done that but I need to get to 220. I'm getting over 4 million.

This is the current code:

double number = 12.0;

cout << number << "! = ";
double y = number;

for (double i = 1; i <y; ++i)
	{
		number = number * (y - i);


	}
cout << number;

I don't know how to take this result and get the result of using it in this formula:

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

Basically I don't know how to make it into this

12!
-------
3!(12-3)!

[mbozzi]

Write a function which computes the factorial of a given integer argument.

Then, write your code in terms of it:

int nCr(int n, int r) 
{ return factorial(n) / factorial(r) / factorial(n - r); }

Note that an implementation like the above imposes some constraints on the caller. In particular, we require that n and r are both nonnegative, that n >= r, and that both factorial(n) and factorial(r) are not too big for the implementation's int type. If any of these preconditions are violated, then the caller has made a programming error.

This is fine, as long as we're sure to communicate these requirements (sometimes called the contract) to the caller.

[keskiverto]

@mbozzi: The instructions tell to use double (to avoid integer overflow).

@JStinsch: You already had:

double students = 12.0;
double teams;
double teamSize = 3.0;

The n is students.
The r is teamSize.

You could use a helper variable for (n - r):
auto diff = students - teamSize;

Then you'll have:
teams = factorial(students) / factorial(teamSize) / factorial(diff);


Note that the input values (n and r) should probably be integers, for real life gets a bloody mess, if you can have 11.4 students ...


A floating point value is not good as a loop counter. Floating point math is not quite intuitive.
Keep the counter as int and make a double form it in the body of the loop, if necessary.


Making that function double factorial(int) and calling it three times is (ought to be) very clear. It is good practise to write that version.

Then consider efficiency
https://en.wikipedia.org/wiki/Factorial#Applications discusses your problem, but seems to compute less.

In this case (n-r) > r, because 9 > 3.

12!
--- = 10 * 11 * 12 = x
 9!

 x
--- = 220
 3!

We did not compute three factorials. We did compute products of two series (consecutive numbers):

{n-r+1..n}
{1..r}

A product of serie that starts from 1 is factorial.

For that you could write a function that is more generic than the factorial():
double serieproduct( int first, int last );

In fact, the factorial could then be rewritten as:

double factorial( int k )
{
  return serieproduct( 1, k );
}

Unlike calling factorial three times, the serieproduct() version requires checking what to compute.
Lets say that teamSize=8. Therefore, diff=4
We don't want to compute

12!
--- and 8!
 4!

We should compute

12!
--- and 4!
 8!

In other words, the use of if else (or ternary operator ?: ) is necessary.


Then again, as mbozzi did mention, you have to check that 0 < teamSize && teamSize <= students before any computation. That is true for all approaches. There is no point to compute anything, if the input is nonsense.