Do you think IIT Guwahati certified course can help you in your career?
Introduction
This blog will discuss the approach of printing all the permutations of a string. Before jumping on the approach of the problem of printing all the permutations of a given string, let’s first understand what a permutation of a string is,
Permutation : Permutation of string refers to one of the arrangements of all the characters of the string in a manner so that it forms a new string. A string can have N! Number of permutations.
Problem Statement
We need to print all the permutations of the string provided as input.
This approach considers checking all the permutations of string and using the backtracking method to backtrack the previous permutations to make another combination.
Steps of Algorithm
Step 1. Call a ‘getResult’ function, which takes three parameters, a string input, the initial index of the substring, and the last index of the substring on which we need to process.
Step 2. In this function, check for the base case, in which if the left index ‘l’ and right index ‘r’ are equal, then print the string and return.
Step 3. If base is not triggered then, make an iteration using a ‘for’ loop and call for each permutation with passing the string after swapping the characters at ‘lth’ and ‘ith’ index of the string and then calling the ‘getResult’ function.
Step 4. Now again, swap the characters at ‘lth’ and ‘ith’ index of the string ‘input’, which is considered as the backtracking step.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
// Print all the permutations
void getResult(string input, int l, int r)
{
// Base case
if (l == r)
{
cout << input << ", ";
return;
}
// All combinations
for (int i = l; i <= r; i++)
{
// Swap
swap(input[l], input[i]);
// Recursive call
getResult(input, l + 1 , r);
// Swap (backtracking)
swap(input[l], input[i]);
}
return;
}
int main()
{
string input = "code";
int n = input.length();
cout << "All Permutations:- " << endl;
getResult(input, 0, n - 1);
return 0;
}
You can also try this code with Online C++ Compiler
Incall to ‘getResult()’, we are checking all the ‘N!’ number of combinations where ‘N’ is the length of the string, and it takes ‘N’ time to print all the permutations. Therefore the overall time complexity is O(N * N!).
Space Complexity O(R - L)
As we are using extra space of size R - L only, therefore the overallspace complexity is O(R - L), where ‘R’ and ‘L’ are the integral indexes that have been passed in each call to the ‘getResult’ function, and ‘R - L’ means the length of the string.
You should watch this video to know the logic behind this and to understand it better.
Frequently Asked Questions
What is a string?
The string is a data type that is the collection of the characters, and we can traverse the string like an array.
What are the different types of recursions?
There are two types of recursion:- Normal Recursion and Tail Recursion.
What is the swap function used in the code and what is the return type of the function?
‘swap()’ function is an inbuilt function in C++ STL. It is used to swap the variables passed in it. It accepts two mandatory arguments ‘X’ and ‘Y’ which are meant to be swapped. There is no return type of the function, it just swaps the values passed in it.
Conclusion
In this article, we discussed the printing of all permutations of a string and discussed the approach to solve this problem programmatically, the Time and Space Complexity.
7+ registered 
