PROBLEM:
Implement a routine that prints all possible orderings of the characters in a string. In other words, print all permutations that use all the characters from the original string. For example, given the string “hat", your function should print the strings "tha", "aht", "tah", "ath", "hta", and "hat". Treat each character in the input string as a distinct character, even if it is repeated. Given the string "aaa", your routine should print "aaa" six times. You may print the permutations in any order you choose.
SOLUTION:
vector<string>& permutate(const string& str, const PERMUTATION& kind, const string& in_probs, string form, int id)
{
static vector<string> remuts;
static int callingTimes = 0;
callingTimes++;
if (id >= str.length())
return remuts;
string probs = form.length() <= 0 ? str : in_probs;
for (int x = 0; x < probs.length(); x++)
{
string nform = form + probs[x];
if (nform.length() == str.length() || kind == COMBINATIONS_NO_ORDER)
{
//Display new ocurance
remuts.push_back(nform);
cout << nform << endl;
}
if (kind == NORMAL_OCCURANCES)
{
//OUTPUT: has same str length regardless of characters order, avoiding redundant of the same character in single ocurance (e.g.: "aat" of "hat" is wrong)
//remove Xth-char from the new prob string to get all next occurances
string nprobs = probs.substr(0, x) + probs.substr(x + 1, probs.length() - (x + 1));
if (nprobs.length() > 0 && id + 1<str.length())
permutate(str, kind, nprobs, nform, id + 1);//non-repeated occurances
}
else if (kind == COMBINATIONS_NO_ORDER)
{
//OUTPUT: has deferent lengths, deferent characters orders not allowed, avoiding redundant of the same character in single ocurance (e.g.: "aat" of "hat" is wrong and "at" with "ta" is wrong)
//remove [0,1, .. ,Xth_char] from new prob string to prevent simillar-reordered combinations
string nprobs = probs.substr(x + 1, probs.length() - (x + 1));
if (nprobs.length() > 0 && id + 1<str.length())
permutate(str,kind, nprobs, nform, id + 1);//non-repeated occurances
}else if (kind == TRUTH_TABLE)
{
//OUTPUT: has same str length regardless of characters order, allow redundant of the same character in single ocurance (e.g.: "aaa" of "hat" is correct)
//use the same set of charaters in the new passed prob to allow output looks liks truth table.
permutate(str, kind, probs, nform, id + 1);//all occurances
}
}
if (form.length() == 0)
cout << "Permutations:" << remuts.size() << ", callingTimes:" << callingTimes << endl;
return remuts;
}
