CC150 9.5

9_5.cpp

/* 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;
}

output

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