#include <iostream> #include <string> using namespace std; int main() { string word; cin>>word; int s = word.size(); string original_word = word; do { for(decltype(s) i =1; i!= s;++i){ auto temp =word[i-1]; word[i-1] = word[i]; word[i] = temp; cout<<word<<endl; } }while(word!=original_word); } Is this solution efficient and how does it compare by doing this recursively?
Edit: When I tested the program it displayed all permutations i.e cat produced: cat act atc tac tca cta
Let's imagine tracing this code on the input 12345. On the first pass through the do ... while loop, your code steps the array through these configurations:
21345 23145 23415 23451 Notice that after this iteration of the loop finishes, you've cyclically shifted the array one step. This means that at the end of the next do ... while loop, you'll have cyclically shifted the array twice, then three times, then four times, etc. After n iterations, this will reset the array back to its original configuration. Since each pass of bubbling the character to the end goes through n intermediary steps, this means that your approach will generate at most n2 different permutations of the input string. However, there are n! possible permutations of the input string, and n! greatly exceeds n2 for all n ≥ 4. As a result, this approach can't generate all possible permutations, since it doesn't produce enough unique combinations before returning back to the start.
If you're interested in learning about a ton of different ways to enumerate permutations by individual swaps, you may want to pick up a copy of The Art of Computer Programming or search online for different methods. This is a really interesting topic and in the course of working through these algorithms I think you'll learn a ton of ways to analyze different algorithms and prove correctness.
std::next_permutation()std::next_permutation()on the string. It's correct and it should be fairly efficient.