Permutation Question

This is a discussion on Permutation Question within the C++ Programming forums, part of the General Programming Boards category; Write a function that returns the number of permutations of the n objects taken k at a time. The function ...

  1. #1
    Registered User
    Join Date
    Oct 2005
    Posts
    16

    Permutation Question

    Write a function that returns the number of permutations of the n objects taken k at a time.

    The function is int permute(int n; int k).

    Example:

    Consider the set of digits 1,2,3, the different permutations of two digits are 1,2,2,1,1,3,2,3,3,2.

    Function makes use of: n!/(n-k)!

    I think I have to make a for loop to compute n! and then I'm guessing another for loop for (n-k)! and then divide these two.

    The code that I have so far is:
    Code:
    int permute(int n; int k)
    {
    int factn;
    int factk;
    
    if(n == 0) 
    {
    factn = 1;
    }
    else
    {
    factn = n * permute(n - 1);
    factk = k * permute(k  1);
    }
    return permute(factn / factk);
    }
    I'm not sure if this code is correct though or if there is an easier way to do it. Please help me out.

  2. #2
    Moderately Rabid Decrypt's Avatar
    Join Date
    Feb 2005
    Location
    Milwaukee, WI, USA
    Posts
    300
    First off, your function doesn't initialize n or k, so you're going to have a problem there.
    Second, your function takes two parameters, n and k - so you can't call permute(n) or permute(k). Or permute(factn / factk).
    A better solution would seem to be two functions, one to find the factorial (n!), and one to find the permuation (n!/(n-k)!).

    *edit* That's to find the number of permutations, to find the actual permutations of a given set is a different story.
    There is a difference between tedious and difficult.

  3. #3
    C++ Newbie
    Join Date
    Nov 2005
    Posts
    49
    I think I've got it, somewhere in my function table, an old permutation function.

    Code:
    int permutation(int n, int k) {
      if((n < 0) || (k < 0) || (n < k)) {
        return 0;
      }
      int p = 1;
      for(int i = 1; i <= k; ++i, --n) {
        p *= n;
      }
      return p;
    }
    Well, this thing find the permutation of a set, but it can't display the actual set though, is this something your looking for? If not, you can use it anyways.

    e+: Your function parameters is seperated by a semi-colon, not good, should be a comma.

  4. #4
    Registered User
    Join Date
    Mar 2005
    Posts
    140
    ^

    Code:
    int perm(int n, int k) {
        int i, perm=n;
    
        if(n == 0) {
           return 1;
        }
    
        for(i=n-1; i>n-k; i--) {
           perm *= i;
        }
    
        return perm;
    }
    perm(5,2)
    Code:
    5*4*3*2*1
    ----------  = 5 * 4
      3*2*1

  5. #5
    C++ Enthusiast jmd15's Avatar
    Join Date
    Mar 2005
    Location
    MI
    Posts
    532
    Well hey, I didn't read all of the above posts but why not use next_permutation if you want to find the actual permutations? Example is a program I wrote to get all the combos(or hopefully all) of a scrambled word. Here is the code:
    Code:
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    int main()
    {
        int count=0;
        char word[256]={0};
        cout<<"Enter a scrambled word: ";
        cin>>word;
        sort(word,word+strlen(word));
        system("cls");
        while(next_permutation(word,word+strlen(word)))
        {
             cout<<word<<endl;
             count++;
        }
        cout<<endl<<count<<" permutations displayed\n";
        cout<<"(Scroll up to see all listed permutations)\n";
        system("PAUSE");
        return 0;
    }
    I use the algorithm sort to sort the scrambled word into alphabetical order, then while next_permutation returns true I display the permutation and add to the count. Then in the end all the permutations have been displayed and I have a variable with the number of permutations.
    Trinity: "Neo... nobody has ever done this before."
    Neo: "That's why it's going to work."
    c9915ec6c1f3b876ddf38514adbb94f0

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Alice....
    By Lurker in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 06-20-2005, 02:51 PM
  2. Debugging question
    By o_0 in forum C Programming
    Replies: 9
    Last Post: 10-10-2004, 05:51 PM
  3. Question about pointers #2
    By maxhavoc in forum C++ Programming
    Replies: 28
    Last Post: 06-21-2004, 12:52 PM
  4. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM
  5. Question, question!
    By oskilian in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 12-24-2001, 12:47 AM

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