Permutation Question

**JHaney** · 11-18-2005

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.

**Decrypt** · 11-18-2005

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.

**Frost Drake** · 11-18-2005

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.

**spydoor** · 11-18-2005

^

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

**jmd15** · 11-18-2005

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.

Thread: Permutation Question

Thread Tools

Search Thread

Display

Permutation Question

Similar Threads

Alice....

Debugging question

Question about pointers #2

Question...

Question, question!