List all permutations of a given string in dictionary order in C++

Understanding String Permutations

String permutations refer to all possible arrangements of characters in a given string. The dictionary order means sorting them lexicographically.

We will explore three different methods to list all permutations of a given string in C++.

Method 1: Using Recursion

This method generates permutations recursively by swapping characters.

#include <iostream>
#include <algorithm>
using namespace std;

void permute(string str, int l, int r) {
    if (l == r)
        cout << str << "\n";
    else {
        for (int i = l; i <= r; i++) {
            swap(str[l], str[i]);
            permute(str, l + 1, r);
            swap(str[l], str[i]);
        }
    }
}

int main() {
    string str = "abc";
    permute(str, 0, str.size() - 1);
    return 0;
}
            

Method 2: Using Next Permutation

This method generates permutations in lexicographical order.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    string str = "abc";
    sort(str.begin(), str.end());
    do {
        cout << str << "\n";
    } while (next_permutation(str.begin(), str.end()));
    return 0;
}
            

Method 3: Using STL

This method sorts the string and uses C++'s next_permutation function.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    string str = "abc";
    sort(str.begin(), str.end());
    cout << str << "\n";
    while (next_permutation(str.begin(), str.end())) {
        cout << str << "\n";
    }
    return 0;
}