-
Permutation (Perplexed)
Hi all,
Can someone please explain why the following short code works in a forward way, but not in reverse order?
For example: if 1234 is entered, the program generates and prints out correct number permutations, but if 4321 is entered it only prints one permutation, as 4321, why??
The same goes for abcd - dcba.
Thanks for any help and enlightenment. Compiler Dev-C++
//permutation
#include <iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;
int main()
{
char v[] = {0};
cout << "Enter a string: ";
cin >> v;
unsigned slen, len = strlen(v);
unsigned c = 1;
for(slen = 1; slen <= len; slen++)
{
c *= slen;
}
cout << v << '\t';
while(next_permutation(v, v+len))
{
cout << v << '\t';
}
cout << endl << "\nTotal of perms = " << c << endl << endl;
system("PAUSE");
return 0;
}
-
When you want the permutations in reverse order use prev_permutation instead of next_permutation.
-
Your lucky that code works at all
snip-----------
char v[] = {0};
cout << "Enter a string: ";
cin >> v;
unsigned slen, len = strlen(v);
unsigned c = 1;
-------------------
you make the string 1 byte long. When the user enters text it is goin to overflow that buffer, suprising it hasent crashed yet.
What is an unsigned?
i think you mean unsigned int
-
Salem:
The next_permutation code is in with algorithm header which comes with Dev-4C++. The code I posted above compiled and worked, but only if the input in a consective number or consective alpha, like abcdef or 12345. When input is mixed, like asdfg and 7459 it does not work properly. Any idea any body I am absolutely baffled! - Thanks for answering.
-
Code:
string input;
cout << "Enter data:";
cin >> input;
while( next_permutation(input.begin() , input.end() ) )
{
cout << input << endl;
}
return 0;
I used this code and it worked perfectly has expected.
If you enter a 3 digit number there are 6 total possible permutations.
If you enter a 4 digit number there are 24 total possible permutations. The next_permutation function computes the next possible permutation in order.
If you enter 123 you get
132
213
231
312
321
as output
But if you enter 213 you only get
231
312
321
as output, becuase those are the only permutations that come after 213.
You can mix numbers and letters, but it uses the ascii value.
If you want to find ALL permutations of a given input, you must make a copy of the input, have one loop start at input and use prev_permutation and have another loop use next permutation.
If this doesn't clear things up, post the code you are having problems with. The first code you posted had some bugs, which i mentoned before.
-
RpiMatty:
Thanks for your comment and example of the program. Yeah, I was expecting the program to generate permutation for any given input from scratch. Do you think you could supply me with onather example of your suggestion of using two loops, prev_permutation and next_permutation? or will it easier to rewrite the code from scratch, hence reinventing the wheel?
Oh come on any other expert coders, please give some help?
Many thanks in anticipation.
-
Like this -
Code:
string input, input1;
cout << "Enter data:";
cin >> input;
input1=input;
while( prev_permutation(input.begin() , input.end() ) )
{
cout << input << endl;
}
while(next_permutation(input1.begin(), input1.end() ) )
{
cout << input1 << endl;
}
You'll may want to check for duplicate characters.
-
zen:
What are the include header files to use for string, begin(); and end(); - I compiled your code, but the Dev4-C++ threw up a lot of complaints. Here your code I tried to compiled. Thanks for your help.
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cstring>
using namespace std;
int main()
{
string input, input1;
cout << "Enter data:";
cin >> input;
input1=input;
while( prev_permutation(input.begin() , input.end() ) )
{
cout << input << endl;
}
while(next_permutation(input1.begin(), input1.end() ) )
{
cout << input1 << endl << endl;
}
system("PAUSE");
return 0;
}
-
-
Many thanks zen, and happy New Year to all who helped. Program works properly now. One more question, can I use this permutation to solve, say what is an anagram of supersonic? - an answer is repercussion. It seems I need to store input and input1 into an array before I can compare an answer to the input question? Any suggestions, bright ideas? - Thanks.
-
repercussion is an anagram of supersonic....... lol
are you sure......
you can use next_permutation and prev_permutation to do what you want as zen has shown you but it will never turn supersonic into repercussion. lol
-
Stoned_Coder:
Sorry, I meant turn supersonic to percussion in anagram. Will post the code sometime later...Thanks for pointing it out.