Permutations of a string

Problem

Write a method to print all the permutations of a given string. In computer science, a permutation refers to the arrangement or ordering of elements in a set or sequence. For example:

Given a set {1, 2, 3}:
The permutations of this set would be: 
{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, and {3, 2, 1}.

Each of these permutations represents a unique arrangement of the elements. Total number of permutations of a set will always be n! where n is the size of the set and all elements of the set are unique.
Practice Problem – LeetCode

Sample Input

s = abc

Sample Output

abc
acb
bac
bca
cab
cba

Approach I

Hypothesis
permute(s, n) will print all the permutations of string s where s.length() = n

Base Case

n = 1
s = a
Permutations: a

Case II

n = 2
s = ab
Permutations: ab, ba

Expectation
permute(s, n-1) will print all the permutations of string s where s.length() = n-1

Induction
We need to print all the permutations of string s where s.length() = n ie. permute (s, n) using permute(s, n-1)

Explanation

Consider case n = 2, s = ab:
permute(s, 1) = a
permute(s, 2) (using permute(s, 1)) :
 char ch = s[n-1] = b

 // place remaining character (ch) 
 // at each position of all the strings in permute(s, 1)
 permutations = ba, ab

Consider case n = 3, s = abc:
permute(s, 2) = ba, ab
permute(s, 3) (using permute(s, 2)) :
 char ch = s[n-1] = c
 permutations = cba, bca, bac; cab, acb, abc;

Pseudocode

Permute(s, n)
permutations[] = {}

if (s.empty() || n == 0):
 return permutations

char ch = str[n-1]
s[] = Permute(s, n-1)

for each str in s[]:
 for each i: 0 to n-1
  String ans = str
  Insert ch(remaining character) at position i to ans
  permutations.add(ans)

return permutations

Code Implementation

//
//  main.cpp
//  Permutations
//
//  Created by Himanshu on 30/05/23.
//

#include <iostream>
#include <string>
#include <vector>
using namespace std;


void printPermutations(vector<string>& permutations) {
    for (const string& permutation : permutations) {
        cout<<permutation<<endl;
    }
}

vector<string> generatePermutations (string s, int n) {
    
    vector<string> permutations;
    
    if (s.empty() || n == 0) {
        permutations.push_back("");
        return permutations;
    }

    char ch = s[n-1];
    vector<string> words = generatePermutations(s, n-1);
    
    for (auto str: words) {
        for (int i = 0; i<n; i++) {
            string ans = str.substr(0, i) + ch + str.substr(i);
            permutations.push_back(ans);
        }
    }
    
    return permutations;
}

int main() {
    string s = "abc";

    vector<string> permutations = generatePermutations(s, (int) s.size());
    
    cout<<"Permutations of string "<<s<<":"<<endl;
    printPermutations(permutations);

    return 0;
}

Output

Permutations of string abc:
cba
bca
bac
cab
acb
abc

Time Complexity: O(n!)

Approach II

Note: You could see how in Layer 1, str[l] ie str[0] or 'a' is placed at all the locations i = {0, 1, 2}. Similarly in Layer 2, as str[0] is fixed, str[1] or 'b' is placed at all the locations i = {1, 2}.

Explanation

Intuition and logic behind the solution:

1. The generatePermutations function takes 3 parameters: input string s, the starting index of the current permutation, l, and the ending index of the current permutation, r.
2. The base case of the recursion is when l becomes equal to r, indicating that a permutation has been generated. In this case, the current permutation is printed.
3. The for loop iterates from l to r, representing the range of characters that can be placed at index l. Each iteration selects a character from this range and swaps it with the character at index l.
4. After the swap, the generatePermutations function is recursively called with l + 1 as the new starting index, effectively fixing the character at index l and generating permutations for the remaining characters.
5. Once the recursive call returns, the swap operation is performed again to restore the original order of characters before moving to the next iteration of the loop. This is known as backtracking.
6. The process continues until all possible permutations are generated.

Pseudocode

generatePermutations(input: string, l: integer, r: integer)
    if l == r then
        print input
        return

    for i from l to r do
        swap input[l] with input[i]
        generatePermutations(input, l + 1, r)
        swap input[l] with input[i]


findAllPermutations(input: string)
    n = length(input)
    generatePermutations(input, 0, n - 1)

Code Implementation

//
//  main.cpp
//  Permutations
//
//  Created by Himanshu on 30/05/23.
//

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

void generatePermutations(string str, int l, int r) {
    
    if (l == r) {
        cout<<str<<endl;
        return;
    }

    for (int i = l; i <= r; ++i) {
        swap(str[l], str[i]);
        generatePermutations(str, l + 1, r);
        swap(str[l], str[i]); //Backtrack
    }
}

void findAllPermutations(::string str) {
    int n = (int) str.length();
    generatePermutations(str, 0, n - 1);
}

int main() {
    string s = "abc";
    
    cout<<"Permutations of string "<<s<<":"<<endl;
    findAllPermutations(s);
    
    return 0;
}

Output

Permutations of string abc:
abc
acb
bac
bca
cba
cab

Time Complexity: O(n!)