-
Permutations
I have been a member here for a while but haven't done any programming in a long while. I never got very far when I tried before but now I am older and wiser so I thought I would give it another shot. I have flicked through the first couple of chapters of the SAMS 24 hour book that I have and I wanted to try a program so I have done the permutations challenge on this site.
This is the function I came up with:
Code:
void permutations (string input)
{
int length = input.size();
char permute [length];
int temp = input.copy(permute,length,0);
permute[temp]='\0';
int count0 = 0;
int count1 = 0;
int count2 = 1;
char temp1;
char temp2;
while (count0 < length)
{
while (count1 <= length - 2)
{
temp1 = permute[count1];
temp2 = permute[count2];
permute[count1] = temp2;
permute[count2] = temp1;
cout << permute << "\n";
count1++;
count2++;
}
count1 = 0;
count2 = 1;
count0++;
}
}
So the function takes a string that the user has inputted and then finds the various permutations of the string by taking the character at the front and then pushing it back a place and outputting the result each time it is pushed back until it outputs the original string at the end.
Have I done this in a very cumbersome way? Are there better ways I should do it?
One thing I don't understand is the use of the string copy function, at first I was calling it without putting the result into a variable, but this added characters, why is this? And why do I have to use it the way I have, I copied it from cpluplus.com where it showed how to use string::copy.
-
I can only tell you that this is code that uses an extension.
Local arrays whose size is not determined by a constant expression (something the compiler can figure out at a compile time), is not possible is regular C++.
You should instead replace it with std::vector.
std::vector<char> permute(length);
-
I haven't seen the challenge on this site (you could add a link to it in your post to help others find it quickly), but that can't be evaluating permutations. Those loops are O(n*n) but permutations are on the order of O(n!).
Basically to evaluate all permutations you should use a recursive function. Permutations are all about trying every item in every position, and then same for the next item, and again for rest of them.