Permutation Calculation

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 06-11-2003
Eric Hansen
Permutation Calculation
I'm currently working on a calculator that figures the permutation and combination.

The only problem I have is the factorial part. I don't know how I'd set that up.

In just incase you don't know what I'm talking about, here's an example of permuation and combination:

Code:

```Combination: nCr [ n! / (n-r)!r!] Permutation: nPr [ n! / (n-r)!] Examples: nCr // n = 5, r = 2 5C2 = 5! / (5-2)!2! = 5! / 3!2! = 5*4*3*2 / 3*2*2 = 5 * 2 = 10 nPr // n = 5, r = 2 5P2 = 5! / (5-2)! = 5! / 3! = 5 * 4 * 3 * 2 / 3 * 2 = 5 * 4 = 20```
*Note that the [ ] 's aer in there because (n! / (n-r)!r!) would be a lil' confusing for me.
• 06-11-2003
PJYelton
While there may be a function in math.h for factorials, you could use a simple for loop to do it yourself:
Code:

```int fact(int x) {     int f=1;     for (int i=x; i>1; i--)     {         f*=i;     }     return f; }```
And if you are using bigger numbers you could use longs or int64's or whatever will handle your limit.
• 06-11-2003
Eric Hansen
Quote:

Originally posted by PJYelton
While there may be a function in math.h for factorials, you could use a simple for loop to do it yourself:
Code:

```int fact(int x) {     int f=1;     for (int i=x; i>1; i--)     {         f*=i;     }     return f; }```
And if you are using bigger numbers you could use longs or int64's or whatever will handle your limit.

Thank you.

I was starting to use a do...while loop, but then I couldn't get the factorial part. I'll search math.h and try your idea, thanks again.
• 06-11-2003
revelation437
when i first read this message, i thought it said
"premature calculation"
and i started laughing SO hard at work...
people were looking at me weird :(
• 06-11-2003
Eric Hansen
Quote:

Originally posted by revelation437
when i first read this message, i thought it said
"premature calculation"
and i started laughing SO hard at work...
people were looking at me weird :(

Sorry for the following, but....ROFL. Honestly, when I first say it in my Math book (yes, I'm a high-schooler), I thought it said the same.

BTW: So far the for(...) loop hasn't done anything.
• 06-11-2003
revelation437
ah its ok. i got a very good laugh outta it
• 06-11-2003
hk_mp5kpdw
Sounds like you need to create a function that will return the factorial of a given number. You can go with either a recursive or non-recursive solution to this.

After seeing Eric's response back to PJYelton's post re while loops: The non-recursive method below uses a while loop. I tested it on my machine and they both work from fact(0) through fact(12) = 479,001,600.

Recursive:
Code:

```unsigned long fact( unsigned long n ) {     if( n == 0 ) return 1;     else if( n <= 2 ) return n;     else return n * fact(n-1); }```
Non-recursive:
Code:

```unsigned long fact( unsigned long n ) {     unsigned long value = (n == 0) ? 1 : n;     while( n >= 2 ) value *= --n;     return value; }```
• 06-11-2003
Murschech
You have touched upon one of my very favorite topics. DO NOT COMPUTE FACTORIALS! The formula you give for nCr is correct but should never be used for computing (except for tiny values of n and r.)
For instance, if you were to use your formula with n=50 and r = 49 you'd have to compute 49!, although the answer is 50. Even unsigned long integers won't work here. So what do you do? You can easily write a program based on Pascal's triangle, that is, based on the relation

nCr = (n-1)C(r-1) + (n-1)Cr

Another way (if you're not comfortable with recursion) is to use the formula

nCr = (n/r)*( (n-1)/(r-1) )*...*( (n-r+1)/1 )

Let me know if you need help with the code
• 06-11-2003
Eric Hansen
Thanks for while loop, and it workED, until I added the 'r' part of the permuation.

Here's my code so far:

PHP Code:

``` #include "includes.h" int pc;  // used for the choice of either permutation or combination int n2; int r2; int ans; unsigned long factn( unsigned long n ); unsigned long factr( unsigned long r ); unsigned long factn( unsigned long n ) {     if( n == 0 ) return 1;     else if( n <= 2 ) return n;     else return n * factn(n-1); } unsigned long factr( unsigned long r ) {     if( r == 0 ) return 1;     else if (r <= 2) return r;     else return r * factr(r-1); } void s_p() {     system("cls");     cout << " nPr = n! / (n-r)!\n";     cout << " n = ";     cin  >> n2;     cout << " r = ";     cin  >> r2;          permutation(int(factn(n2)), int(factr(r2))); } void permutation(int n, int r) {     cout << factn(n) << " --- " << factr(r) << "\n\n"; }  ```
*NOTE: This doesn't contain ALL the code, just the calculation portion.

It runs fine, the only problem is the math. if n = 5, and r = 2, then the answer will be 0 --- 2 (the --- is just for my own comfort).
• 06-11-2003
revelation437
whoa
nice first post
• 06-11-2003
Eric Hansen
Quote:

Originally posted by Murschech
You have touched upon one of my very favorite topics. DO NOT COMPUTE FACTORIALS! The formula you give for nCr is correct but should never be used for computing (except for tiny values of n and r.)
For instance, if you were to use your formula with n=50 and r = 49 you'd have to compute 49!, although the answer is 50. Even unsigned long integers won't work here. So what do you do? You can easily write a program based on Pascal's triangle, that is, based on the relation

nCr = (n-1)C(r-1) + (n-1)Cr

Another way (if you're not comfortable with recursion) is to use the formula

nCr = (n/r)*( (n-1)/(r-1) )*...*( (n-r+1)/1 )

Let me know if you need help with the code

Pascal's triangle is a great choice....and before I go any further, I know what it is. My question on that though, how would I even set it up? Arrays would take to long, wouldn't they?
• 06-11-2003
hk_mp5kpdw
Based on the formula you gave for permutations, you don't need two seperate factorial functions. Just get the n and r values and then do something like:
Code:

```cout << "Enter n and r followed by [Enter]: "; cin >> n >> r; cout << "Permutation is " << fact(n)/fact(n-r) << endl;```
Notice you can call the same exact function, just with different arguments, and do the division all within the output statement.
• 06-11-2003
Eric Hansen
Quote:

Originally posted by hk_mp5kpdw
Based on the formula you gave for permutations, you don't need two seperate factorial functions. Just get the n and r values and then do something like:
Code:

```cout << "Enter n and r followed by [Enter]: "; cin >> n >> r; cout << "Permutation is " << fact(n)/fact(n-r) << endl;```
Notice you can call the same exact function, just with different arguments, and do the division all within the output statement.

Thank you. I'll try that, and see how it works.

[EDIT]
That works, and here's the new code:
PHP Code:

``` #include "includes.h" int pc; int n2; int r2; int ans; unsigned long fact( unsigned long n ); unsigned long fact( unsigned long n ) {     if( n == 0 ) return 1;     else if( n <= 2 ) return n;     else return n * fact(n-1); } void s_p() {     system("cls");     cout << " nPr = n! / (n-r)!\n";     cout << " n = ";     cin  >> n2;     cout << " r = ";     cin  >> r2;          permutation(fact(n2), fact(n2-r2)); } void permutation(int n, int r) {     ans = n / r;     cout << "\n\n" << ans; }  ```
Soon I'll start work on the Combination...should be easier now since I got the permutation code working (thanks to all who tried/helped me).
[/edit]
• 06-11-2003
Eric Hansen
Ok, here's the program (with source). I know there's probably some errors, but any input would be greatly appreciated.

NOTE: The close function goes on 2x (a.k.a.: I used system("PAUSE"); twice, and it displays twice).
• 06-11-2003
moonwalker
your program crashes if you try to choose r > n
and do nPr

you should use an if condition to check this and prevent people from entering r > n.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last