# Another permutator

This is a solution to this problem. The problem statement:

write a program to display all possible permutations of a given input string--if the string contains duplicate characters, you may have multiple repeated results. Input should be of the form

permute string

and output should be a word per line.

This is my code:

#include <iostream>
#include <string>
#include <vector>

std::vector<std::string> permute(std::string s) {
std::vector<std::string> retval;
if (s.length() <= 1) {
retval.push_back(s);
return retval;
} else {
for (size_t i = 0; i < s.length(); ++i) {
std::rotate(s.begin(), s.begin() + 1, s.end());
for (std::string permutation : permute(s.substr(1, std::string::npos))) {
retval.push_back(s.substr(0,1).append(permutation));
}
}
return retval;
}
}

int main(int argc, char **argv) {
std::string toPermute;
if (argc < 2) {
std::cout << "Please enter a word to permute:" << std::endl;
std::cin >> toPermute;
} else {
toPermute = argv;
}

std::vector<std::string> result = permute(toPermute);

std::cout << "Number of permutations: " << result.size() << std::endl;
std::cout << std::string(24, '=') << std::endl;

for (std::string permutation : result) {
std::cout << permutation << std::endl;
}
}

• Look at std::next_permutation() The number of permutations of a string is factorial(string.size()) – Martin York Aug 1 '14 at 23:47
• Yes, std::next_permutation is in one of the answers already. I only included the number of permutations to be able to verify the algorithm generated the right number (by computing the factorial) so replacing that with the factorial function would sort of defeat the purpose. @LokiAstari – 11684 Aug 2 '14 at 7:47

• Technically, the code doesn't meet the requirements: displaying number of permutations is not requested. You may add an option to display it as well, but a simple invocation permute string shall display only the permutations.

• Returns from permute: a non-void function with no return at the very end may raise some eyebrows.

Just extract return retval; out of if/else construct:

if (s.length() <= 1) {
retval.push_back(s);
} else {
...
}
return retval;

• Algorithm has exponential time complexity. It is OK, because of the nature of task. It also requires exponential amount of memory, and it is not OK. You are not asked to keep all permutations, you just need to display them. And there is a solution with constant memory requirements.

Instead of using a loop to display the vector, you can just use iterators:

std::copy(result.begin(), result.end(),
std::ostream_iterator<std::string>(std::cout, "\n");


(this requires both <algorithm> and <iterator>)

I've also used \n here since you really don't need to use std::endl in so many places.

Your permutation work could really be simplified by using std::next_permutation** in <algorithm>.

void displayStringPermutations(std::string str, std::ostream& stream, const std::string& delim) {
std::sort(std::begin(str), std::end(str));

do {
stream << str << delim;
}
while (std::next_permutation(std::begin(str), std::end(str)));
}


Adapting this to return a std::vector<std::string> of permutations or generalizing for any Container::value_type for re-usability pretty much takes the same form.

**std::next_permutation will return the next higher permutation. It is well within the definition of this problem as your problem stipulates that it "may have multiple repeated results" and not that it "should have multiple repeated results".

• Thank you. If this was 'real' code I certainly should have used that, but the point of this exercise was to implement a permutation algorithm. Nonetheless, it's good to know it exists. – 11684 Jul 31 '14 at 21:08
• To be on-topic on CodeReview, your original post should be 'real' code. With a c++11 tag and your use of std::rotate, I felt the response was appropriate and applicable for the purposes of CodeReview. – Snowhawk Jul 31 '14 at 22:03
• @Snowhawk04: I added that tag myself since the OP was using range-based for loops. – Jamal Jul 31 '14 at 22:29