By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,421 Members | 1,089 Online
Bytes IT Community
+ Ask a Question
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
  1. #include <iostream>                 //Required if your program does any I/O
  2. #include <string>                   //Required if your program uses C++ strings
  3. #include <algorithm>                // next_permutation() via stl_algo.h
  4. #include <vector>                   // stl vector header
  5. #include <iterator>                 // ostream_iterator
  6. using namespace std;                //Required for ANSI C++ 1998 standard.
  7.  
  8.  
  9. int main (int argc, char **argv)    //Arguments to main are command line arguments
  10. {
  11.     char reply;                     //A character variable to hold user input
  12.     string something;
  13.     vector<char> iV;
  14.  
  15.  
  16.     cout << "Enter a string: ";
  17.     cin >> something;
  18.  
  19.     //Take every single letter in the string and put it into vector
  20.     for(int x = 0; x < something.length(); x++)
  21.     {
  22.           iV.push_back(something[x]);
  23.     }
  24.  
  25.     // display original
  26.     cout << "\nOriginal string:\n";
  27.     copy(iV.begin(),iV.end(),ostream_iterator<char>(cout,""));
  28.  
  29.     cout << "\n\nPermutations:\n";
  30.     // loop until all permutations are generated and displayed
  31.     // does not display original string
  32.     while (next_permutation(iV.begin(), iV.end())) 
  33.     { 
  34.             copy(iV.begin(),iV.end(),ostream_iterator<char>(cout,""));
  35.             cout << endl;
  36.     }
  37.  
  38.     // This section stops the program 'flashing' off the screen.
  39.     cout << "\n\nPress q (or any other key) followed by 'Enter' to quit: ";
  40.     cin >> reply;
  41.     return 0;
  42. }
  43.  
Mar 17 '07 #1
Share this Question
Share on Google+
8 Replies


P: 25
This is my output:

Expand|Select|Wrap|Line Numbers
  1. Enter a string: abc
  2.  
  3. Original string:
  4. abc
  5.  
  6. Permutations:
  7. acb
  8. bac
  9. bca
  10. cab
  11. cba
  12.  
  13.  
  14. Press q (or any other key) followed by 'Enter' to quit:
Mar 17 '07 #2

Ganon11
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

Ganon11
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
  1. #include <iostream>                 //Required if your program does any I/O
  2. #include <string>                   //Required if your program uses C++ strings
  3. #include <algorithm>                // next_permutation() via stl_algo.h
  4. #include <vector>                   // stl vector header
  5. #include <iterator>                 // ostream_iterator
  6. using namespace std;                //Required for ANSI C++ 1998 standard.
  7.  
  8.  
  9. int main (int argc, char **argv)    //Arguments to main are command line arguments
  10. {
  11.     char reply;                     //A character variable to hold user input
  12.     string something;
  13.     vector<char> iV;
  14.  
  15.  
  16.     cout << "Enter a string: ";
  17.     cin >> something;
  18.  
  19.     //Take every single letter in the string and put it into vector
  20.     for(int x = 0; x < something.length(); x++)
  21.     {
  22.           iV.push_back(something[x]);
  23.     }
  24.  
  25.     // display original
  26.     cout << "\nOriginal string:\n";
  27.     copy(iV.begin(),iV.end(),ostream_iterator<char>(cout,""));
  28.  
  29.     cout << "\n\nPermutations:\n";
  30.     // loop until all permutations are generated and displayed
  31.     // does not display original string
  32.     while (next_permutation(iV.begin(), iV.end())) 
  33.     { 
  34.             copy(iV.begin(),iV.end(),ostream_iterator<char>(cout,""));
  35.             cout << endl;
  36.     }
  37.  
  38.     // This section stops the program 'flashing' off the screen.
  39.     cout << "\n\nPress q (or any other key) followed by 'Enter' to quit: ";
  40.     cin >> reply;
  41.     return 0;
  42. }
  43.  







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
wwx
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

Post your reply

Sign in to post your reply or Sign up for a free account.