Another permutator

Question

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[1];
    }

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

Answer 1

• 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.

Answer 2

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.

Answer 3

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".