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 <string>
#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.length() - 1);
    return 0;
}
            

Method 2: Using Next Permutation Algorithm

This method generates permutations using the next permutation algorithm.

 
#include <string>
#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 Recursion with Sorting

This method generates and sorts permutations manually.

 
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

void permuteSorted(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]);
            permuteSorted(str, l + 1, r);
            swap(str[l], str[i]);
        }
    }
}

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