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