Permutation Calculation

This is a discussion on Permutation Calculation within the C++ Programming forums, part of the General Programming Boards category; I'm currently working on a calculator that figures the permutation and combination. The only problem I have is the factorial ...

  1. #1
    Registered User
    Join Date
    Jun 2003
    Posts
    18

    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.

  2. #2
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  3. #3
    Registered User
    Join Date
    Jun 2003
    Posts
    18
    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.

  4. #4
    Registered User
    Join Date
    Dec 2002
    Posts
    221
    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

  5. #5
    Registered User
    Join Date
    Jun 2003
    Posts
    18
    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.

  6. #6
    Registered User
    Join Date
    Dec 2002
    Posts
    221
    ah its ok. i got a very good laugh outta it

  7. #7
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,803
    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;
    }
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  8. #8
    Registered User
    Join Date
    Jun 2003
    Posts
    1

    Combinatios alert!

    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

  9. #9
    Registered User
    Join Date
    Jun 2003
    Posts
    18
    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 factnunsigned long n );
    unsigned long factrunsigned long r );

    unsigned long factnunsigned long n )
    {
        if( 
    == ) return 1;
        else if( 
    <= ) return n;
        else return 
    factn(n-1);
    }

    unsigned long factrunsigned long r )
    {
        if( 
    == ) return 1;
        else if (
    <= 2) return r;
        else return 
    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 nint 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).
    Last edited by Eric Hansen; 06-11-2003 at 11:08 AM.

  10. #10
    Registered User
    Join Date
    Dec 2002
    Posts
    221
    whoa
    nice first post

  11. #11
    Registered User
    Join Date
    Jun 2003
    Posts
    18

    Re: Combinatios alert!

    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?

  12. #12
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,803
    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.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  13. #13
    Registered User
    Join Date
    Jun 2003
    Posts
    18
    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 factunsigned long n );

    unsigned long factunsigned long n )
    {
        if( 
    == ) return 1;
        else if( 
    <= ) return n;
        else return 
    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 nint r)
    {
        
    ans 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]
    Last edited by Eric Hansen; 06-11-2003 at 11:28 AM.

  14. #14
    Registered User
    Join Date
    Jun 2003
    Posts
    18
    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).
    Attached Files Attached Files
    Quantum Theory Entertainment

    Team #0005 US FIRST Robotics Team Website Designer
    Contact me on AIM: evanescence s0ul

    Compiler/IDE: Microsoft Visual Studio (C++) 6.0 / Microsoft .NET 2003

  15. #15
    Registered User moonwalker's Avatar
    Join Date
    Jul 2002
    Posts
    282
    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.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem with modulo calculation
    By manutdfan in forum C Programming
    Replies: 6
    Last Post: 01-12-2009, 02:37 PM
  2. bit level permutation function
    By zxcv in forum C Programming
    Replies: 2
    Last Post: 07-27-2008, 01:26 PM
  3. Help with calculation and loop
    By Betty in forum C Programming
    Replies: 7
    Last Post: 04-10-2006, 05:37 AM
  4. Permutation algorithm??
    By lris2005 in forum C++ Programming
    Replies: 1
    Last Post: 04-01-2006, 05:51 AM
  5. INT ARRAY Permutation!
    By arthur5005 in forum C++ Programming
    Replies: 2
    Last Post: 10-21-2002, 05:30 AM

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