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.

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.

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.

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 :(

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.

ah its ok. i got a very good laugh outta it

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

---

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

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

whoa
nice first post

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?

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.

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]

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

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.

Quote:

---

Originally posted by 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.

---

I'm currently fixing that, and came across a lil' problem.

Basically, when you choose #3 on the main menu after the r > n error check (after it displays), the menu shows back up, and then you have to choose #3 again. Here's my new code
(at time of posting):

PHP Code:

---

#include "includes.h"

int pc;        // Used for the choice between permutation, combination, or quiting
int n2;        // n part of nCr and/or nPr
int r2;        // r part of nCr and/or nPr
int ans;    // The answer of permutations or combinations

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";    // Formula definition
    cout << " n = ";                // N value
    cin  >> n2;                        // "  " input
    cout << " r = ";                // R value
    cin  >> r2;                        // "  " input
    
    if(r2 > n2)
    {
        cout << "\n\n" << r2 << " > " << n2 << " doesn't factor out correctly!\n\n";
        cout << "1) Go back to beginning\n"
                " >> ";
        cin  >> ans;
        if (ans = 1) { system("cls"); begin(); }
        if (ans != 1) { system("PAUSE"); }
    }

    begin();

    if(r2 <= n2)
    {
        permutation(fact(n2), fact(n2-r2));    // Figures the permutation
    }
}

void s_c()
{
    system("cls");
    cout << " nCr = n! / (n-r)!r!\n";
    cout << " n = ";
    cin  >> n2;
    cout << " r = ";
    cin  >> r2;

    if(r2 > n2)
    {
        cout << "\n\n" << r2 << " > " << n2 << " doesn't factor out correctly!\n\n";
        cout << "1) Go back to beginning\n"
                " >> ";
        cin  >> ans;
        if (ans = 1) { system("cls"); begin(); }
        if (ans != 1) { system("PAUSE"); }
    }

    if(r2 <= n2)
    {
        combination(fact(n2), fact(n2-r2));
    }
}

void permutation(int n, int r)
{
    ans = n / r;
    cout << "\n\n" << ans << "\n\n";
    system("PAUSE");
    begin();
}

void combination(int n, int r)
{
    ans = n / (r * fact(r2));
    cout << "\n\n" << ans << "\n\n";
    system("PAUSE");
    begin();
}

void begin()
{
    Start:
    cout << " Permutation (1)\n"
            " Combination (2)\n"
            " Exit        (3)\n\n";
    cout << " "; 
    cin  >> pc;

    switch(pc)
    {
    case 1:
        s_p();
        break;

    case 2:
        s_c();
        break;

    case 3:
        system("PAUSE");
        break;

    default:
        cout << "\n" << pc << " is not a valid choice!  Please choose another!\n\n";
        system("PAUSE");
        system("cls");
        goto Start;
        break;
    }
} 


---

I didn't change anything else.

completely OT, but I like the colored code. What are you using to do that?

Quote:

---

Originally posted by blackrat364
completely OT, but I like the colored code. What are you using to do that?

---

OT means???

I'm pressuming you mean the stuff I posted above? I'm using the [ php ] (w/o spaces) and [ /php ] (also w/o spaces). It's VB stuff.

OT means off topic. So if you use the PHP tags for your code, it colors it? Or are you inserting a tag for each color?

Quote:

---

Originally posted by blackrat364
OT means off topic. So if you use the PHP tags for your code, it colors it? Or are you inserting a tag for each color?

---

Ok, quick question, how is it exactly off-topic?

Right, it colors it. Just using the PHP tags.

It's off the topic of permutations

Quote:

---

Originally posted by blackrat364
It's off the topic of permutations

---

This thread will probably break the rules soon because of the "conversation", but I don't see how asking about fixing some code for calculating permutations / combinations is OT from permutations.....

P.S. PM, IM, or E-mail me if you wish to continue this conversation.