Last active
August 29, 2015 14:04
-
-
Save ivycheung1208/1b9a43cf2fa1f5a115eb to your computer and use it in GitHub Desktop.
CC150 9.5
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* CC150 9.5 */ | |
#include <iostream> | |
#include <vector> | |
#include <string> | |
using namespace std; | |
// Steinhaus-Johnson-Trotter algorithm | |
// http://en.wikipedia.org/wiki/Steinhaus-Johnson-Trotter_algorithm | |
// By alternating between descending and ascending placements of n, each permutation differs from | |
// the previous one either by the single-position-at-a-time motion of n, or by a change of two smaller | |
// numbers inherited from the previous sequence of shorter permutations. | |
// In either case this difference is just the transposition of two adjacent elements. | |
// When n > 1 the first and final elements of the sequence, also, differ in only two adjacent elements | |
// (the positions of the numbers 1 and 2). | |
vector<string> getPermutations(string str) | |
{ | |
vector<string> strPmt; | |
if (str.empty()) | |
return strPmt; | |
string newStr(1, str[0]); | |
strPmt.push_back(newStr); | |
bool isEven = false; // flag for even permutation | |
while (strPmt.begin()->size() != str.size()) { // build permutations on n items based on permutations on n - 1 items | |
string currStr = *strPmt.begin(); // get the next n - 1 permutation | |
char newChar = str[currStr.size()]; | |
isEven = !isEven; | |
if (isEven) { // when the permutation on n - 1 items is even | |
for (auto beg = currStr.end(); beg != currStr.begin(); --beg) { // place the number n in all possible positions in descending order | |
auto inserted = currStr.insert(beg, newChar); | |
strPmt.push_back(currStr); | |
beg = currStr.erase(inserted); | |
} | |
currStr.insert(currStr.begin(), newChar); // insert to the begin (will cause iterator decrement error in the loop) | |
strPmt.push_back(currStr); | |
currStr.erase(currStr.begin()); | |
} | |
else { // when the permutation on n - 1 items is odd | |
for (auto beg = currStr.begin(); beg != currStr.end(); ++beg) { // place the number n in all possible positions in ascending order | |
auto inserted = currStr.insert(beg, newChar); | |
strPmt.push_back(currStr); | |
beg = currStr.erase(inserted); | |
} | |
currStr.insert(currStr.end(), newChar); // insert to the end (will cause iterator increment error in the loop) | |
strPmt.push_back(currStr); | |
currStr.erase(currStr.end() - 1); | |
} | |
strPmt.erase(strPmt.begin()); // erase this n - 1 permutation | |
if (strPmt.begin()->size() != currStr.size()) // procede to new level, reset flag | |
isEven = false; | |
} | |
return strPmt; | |
} | |
int main() | |
{ | |
string str; | |
cin >> str; | |
vector<string> strPmt = getPermutations(str); | |
for (auto s : strPmt) | |
cout << s << endl; | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
1234 | |
1234 | |
1243 | |
1423 | |
4123 | |
4132 | |
1432 | |
1342 | |
1324 | |
3124 | |
3142 | |
3412 | |
4312 | |
4321 | |
3421 | |
3241 | |
3214 | |
2314 | |
2341 | |
2431 | |
4231 | |
4213 | |
2413 | |
2143 | |
2134 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment