Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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;
    }
}
share|improve this question
    
Look at std::next_permutation() The number of permutations of a string is factorial(string.size()) –  Loki Astari Aug 1 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 at 7:47

3 Answers 3

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
    
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 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. –  Snowhawk04 Jul 31 at 22:03
    
@Snowhawk04: I added that tag myself since the OP was using range-based for loops. –  Jamal Jul 31 at 22:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.