446,421 Members | 1,089 Online
Need help? Post your question and get tips & solutions from a community of 446,421 IT Pros & Developers. It's quick & easy.

# Help with Permutation

 P: 25 Create a program to display all of the permutations of a string of any length. A permutation is a re-arrangement of the order of letters. For example, the string "abc" has permutations "acb", "bca", "bac", "cab", and "cba" Here is my code but I don't know how to re-arrangement. Please help me Expand|Select|Wrap|Line Numbers #include                  //Required if your program does any I/O #include                    //Required if your program uses C++ strings #include                 // next_permutation() via stl_algo.h #include                    // stl vector header #include                  // ostream_iterator using namespace std;                //Required for ANSI C++ 1998 standard.     int main (int argc, char **argv)    //Arguments to main are command line arguments {     char reply;                     //A character variable to hold user input     string something;     vector iV;         cout << "Enter a string: ";     cin >> something;       //Take every single letter in the string and put it into vector     for(int x = 0; x < something.length(); x++)     {           iV.push_back(something[x]);     }       // display original     cout << "\nOriginal string:\n";     copy(iV.begin(),iV.end(),ostream_iterator(cout,""));       cout << "\n\nPermutations:\n";     // loop until all permutations are generated and displayed     // does not display original string     while (next_permutation(iV.begin(), iV.end()))      {              copy(iV.begin(),iV.end(),ostream_iterator(cout,""));             cout << endl;     }       // This section stops the program 'flashing' off the screen.     cout << "\n\nPress q (or any other key) followed by 'Enter' to quit: ";     cin >> reply;     return 0; }   Mar 17 '07 #1
8 Replies

 P: 25 This is my output: Expand|Select|Wrap|Line Numbers Enter a string: abc   Original string: abc   Permutations: acb bac bca cab cba     Press q (or any other key) followed by 'Enter' to quit: Mar 17 '07 #2

 Expert 2.5K+ P: 3,652 So what are you still trying to do? It looks like you have correctly solved the problem to me. Try testing it with some other strings to see what output you get. Mar 17 '07 #3

 P: 25 With "abc" input My output is: "acb", "bac", "bca", "cab" and "cba" But it should be like this: "acb", "bca", "bac", "cab", and "cba" Mar 17 '07 #4

 Expert 2.5K+ P: 3,652 Does it really matter? You were asked to display the possible permutations of the input string, and you have - the order in which they are displayed should not be an issue. Mar 17 '07 #5

 P: 1 Create a program to display all of the permutations of a string of any length. A permutation is a re-arrangement of the order of letters. For example, the string "abc" has permutations "acb", "bca", "bac", "cab", and "cba" Here is my code but I don't know how to re-arrangement. Please help me Expand|Select|Wrap|Line Numbers #include                  //Required if your program does any I/O #include                    //Required if your program uses C++ strings #include                 // next_permutation() via stl_algo.h #include                    // stl vector header #include                  // ostream_iterator using namespace std;                //Required for ANSI C++ 1998 standard.     int main (int argc, char **argv)    //Arguments to main are command line arguments {     char reply;                     //A character variable to hold user input     string something;     vector iV;         cout << "Enter a string: ";     cin >> something;       //Take every single letter in the string and put it into vector     for(int x = 0; x < something.length(); x++)     {           iV.push_back(something[x]);     }       // display original     cout << "\nOriginal string:\n";     copy(iV.begin(),iV.end(),ostream_iterator(cout,""));       cout << "\n\nPermutations:\n";     // loop until all permutations are generated and displayed     // does not display original string     while (next_permutation(iV.begin(), iV.end()))      {              copy(iV.begin(),iV.end(),ostream_iterator(cout,""));             cout << endl;     }       // This section stops the program 'flashing' off the screen.     cout << "\n\nPress q (or any other key) followed by 'Enter' to quit: ";     cin >> reply;     return 0; }   hi i executed this pgm i got correct result when i give 3 character like abc,cba...... but i got incorrect result when i gave more than three character like dine,jkkl.... pls clarify my doubt Apr 12 '07 #6

 Expert P: 83 From this documentation of next_permutation -- http://www.sgi.com/tech/stl/next_permutation.html -- it seems that the function might not work if your original series is not sorted in non-descending order. It says, "There is a finite number of distinct permutations (at most N! [1], where N is last - first), so, if the permutations are ordered by lexicographical_compare, there is an unambiguous definition of which permutation is lexicographically next." My tests of your code showed that it worked right except for your example "dllk". Try sorting that ("dkll") in the code, and see how it works then. My tests indicate that it works right if you enter "dkll". Apr 12 '07 #7

 Expert P: 83 Re-examining the output, I see that this is the case. The next_permutation function assumes it has finished when the series is in reverse order. (Otherwise it wouldn't know where to stop.) Thus, if you don't start with an ordered series, some of the permutations will be skipped. Apr 12 '07 #8

 P: 2 There are some different algorithms to generate permutation. The common used algorithm is Dictionary Based Method which produce all the permutation in order. So your problem is to find the appropriate method for the permutation which can produce the sequence as you though. Here is a very fast example of permutation that I found on the net : http://ongkowijaya.googlepages.com/O...itudeTests.htm , and it is originally by Johnson et al. I show you this to let you know that your question is a part of the Mathematic World. Dec 8 '07 #9