Permutations are typically believed to be a mathematical topic, although this is not true. Mathematics is important in computer science because it teaches us how to communicate abstractly, work with algorithms, self-analyze our computational thinking, and represent real-world solutions accurately. A permutation of a string is a rearrangement of its characters to create different sequences. It involves changing the order of characters while retaining all the original characters. For example, permutations of "ABC" include "ABC," "ACB," "BAC," "BCA," "CAB," and "CBA." Permutations are often computed recursively or iteratively, generating all possible orders of the characters in the given string.
What is the permutation of string?
A Permutation of string is an arrangement of its characters in a particular order. A new string is created by rearranging the characters of the old string. The number of permutations of a string depends on its length and is determined by the factorial of that length. Permutations are frequently employed in algorithms and tasks such as creating all possible combinations, solving riddles, and analyzing various element arrangements.
Problem Statement
String permutations have applications ranging from security and encryption to optimization and analysis. It allows us to solve complex problems and study varied data configurations. An example of a string permutation is given below. In this example, you have to print all the permutations of the string “abc”. So in the output, you will see all 6 permutations of “abc”.
You are given a string ‘str’ consisting of lowercase letters. Your task is to return all permutations in string in any order.
Sample Input
abc
Sample Output
abc acb bac bca cab cba
Solution Approach
There are various algorithms and techniques to print all the permutations of a string. Some of the optimal ones are explained below.
Print Permutations of a given String using Backtracking
Backtracking is an algorithmic strategy for recursively solving problems by attempting to develop a solution gradually, one step at a time, and discarding any solutions that do not satisfy the problem's criteria at any point in time.
To print all the permutations in the string, backtracking is the most optimal approach. Let’s see with the help of a Recursion tree.
Explanation of the above diagram
We’ll fix one characterat every step then permutations of the remaining characters are written next to them one by one.
Next, we’ll fix two characters, and so on. These steps are followed by writing the permutation of the remaining characters next to the fixed characters.
Algorithm
We’ll define a function generatePermutaionsHelper(Str, l, r). This function will generate the permutations of the substring starting from index “l” and ending at index “r”.
Calling the above function, generatePermutaionsHelper(Str, l, r).
If “l” is equal to “r”, a new permutation is found. Insert this string in the “ans” list.
Else, continue to iterate on the string from “l” to“r”.
Let “i” denote the current index.
Swap Str[ l ] and Str[ i ] to fix the “ith” character on the index ”l”.
Call generatePermutaionsHelper(Str, l + 1, r) to get the permutation of the rest of the characters.
Now, backtrack and swap Str[ l ] and Str[ i ] again.
In the end, we’ll have the list “ans” having all the permutations of the given string. If we want the permutations in lexicographically increasing order, we have to sort the list.
Implementation
#include <bits/stdc++.h>
using namespace std;
void generatePermutationsHelper(string &str, int l, int r, vector<string> &ans)
{
// base case
if (l == r)
{
ans.push_back(str);
return;
}
for (int i = l; i <= r; i++)
{
swap(str[l], str[i]);
generatePermutationsHelper(str, l + 1, r, ans);
// backtrack
swap(str[l], str[i]);
}
}
int main()
{
// stores the permutations of the string
vector<string> ans;
string str = "aac";
int l = 0;
int r = str.size() - 1;
//Empty Input String
if(str.length()==0)
{
cout<<"No Permutations Possible!!";
}
else
generatePermutationsHelper(str, l, r, ans);
// lexicographically increasing order
sort(ans.begin(), ans.end());
for(int i = 0;i<ans.size();i++)
{
cout<<ans[i]<<endl;
}
return 0;
}
You can also try this code with Online C++ Compiler
Time Complexity The time complexity of this approach is O(N!), where N is the length of the string.
Reason: The reason is there are n! permutations and we are generating them one by one. Thus, generating all permutations of a string takes O(N!) time. We are also sorting the “ans” list of size O(N!), which will take O(log(N!)) time.
Thus, the final time complexity is O(log(N!) + N!) ~ O(N!).
Space Complexity The time complexity of this approach is O(N!), Where N is the length of the given string.
Reason: The recursive function uses the O(N) recursion stack. We also store the permutations in a list that occupies O(N!) space. Thus, the final space complexity is O(N + N!) ~ O(N!).
Drawbacks of the above approach
The above approach works fine when all the characters of a string are unique. But if the string has repeated characters this approach will print duplicate permutations as you saw in the above example.
There is a variation of the backtracking approach(mentioned below) to handle the above test case.
Another approach by concatenating Substrings
An alternative approach to finding all permutations of a string is to form each permutation by concatenating substrings of the string, which are generated by removing one character at a time. The base case for the recursive approach would be when the string is empty, at which point we have generated a permutation.
This method can be considered a divide-and-conquer algorithm, as we are "dividing" the problem of generating all permutations into smaller problems of generating permutations of smaller strings.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// Function to generate all permutations of a string
vector<string> generate_permutations(string s) {
// Vector to store all permutations
vector<string> permutations;
// Base case: when the string is empty
if(s.empty()){
permutations.push_back("");
return permutations;
}
// For every character in string
for(int i = 0; i < s.size(); i++){
// Form a string by removing the i'th character
string remaining = s.substr(0, i) + s.substr(i+1);
// Generate all permutations for the remaining string
vector<string> remaining_perms = generate_permutations(remaining);
// For each permutation of the remaining string
for(int j = 0; j < remaining_perms.size(); j++){
// Prepend the current character and append it to permutations
permutations.push_back(s[i] + remaining_perms[j]);
}
}
// Return all generated permutations
return permutations;
}
int main() {
string str = "abc";
vector<string> permutations = generate_permutations(str);
// Print all permutations
for(int i = 0; i < permutations.size(); i++)
cout << permutations[i] << endl;
return 0;
}
Output
abc
acb
bac
bca
cab
cba
This approach also has a time complexity of O(n!), where n is the length of the string. The factorial time complexity arises from the fact that there are n! Permutations of a string of length n. As such, both of these methods can be slow for large strings. However, this method uses more space than the backtracking approach, as it creates many temporary string objects.
Another approach by using itertools package(Python)
Python's itertools library has a function called permutations() that can be used to generate all permutations of a string concisely and efficiently. Here is an example of how you can use it:
import itertools
def generate_permutations(s):
# itertools.permutations returns an iterator yielding tuples, so we join each tuple to form strings
return [''.join(p) for p in itertools.permutations(s)]
def main():
s = "abc"
print("All permutations of the string:")
print(generate_permutations(s))
if __name__ == "__main__":
main()
Output
The time and space complexity for generating all permutations of a string using itertools.permutations() in Python is as follows:
Time Complexity: O(n!) - There are n! Permutations of a string of length n, so the time complexity is factorial in the size of the string.
Space Complexity: O(n) - This approach generates each permutation one at a time, so the space complexity is linear in the string size.
However, please note that the space complexity of the generate_permutations(s) function as written is technically O(n*n!) because it creates a list of all the permutations, and each permutation is a string of length n. If you were to yield each permutation one at a time (by making generate_permutations a generator function or by directly iterating over itertools.permutations(s)), you could reduce the space complexity to O(n).
Another Approach Using Inbuilt STL Function
In C++, the Standard Template Library (STL) provides an inbuilt function std::next_permutation to generate a given string or sequence permutations. This function rearranges the elements in the range [first, last) into the next lexicographically greater permutation.
Here is how you can use std::next_permutation to generate all permutations of a string:
#include <iostream>
#include <string>
#include <algorithm>
int main() {
std::string str = "abc";
// Sort the string in lexicographically ascending order
std::sort(str.begin(), str.end());
// Generate all permutations
do {
std::cout << str << std::endl;
} while(std::next_permutation(str.begin(), str.end()));
return 0;
}
Output
Time Complexity: The time complexity is O(n!), where n is the size of the string. This is because there are n! Permutations of a string of length n, and each call to std::next_permutation takes O(n) time.
Space Complexity: The space complexity is O(1) because this method generates each permutation in place without using any additional space. The only space used is the input string itself.
The number of permutations of a string is always equal to the factorial of the length of the string. For example : string HELLO of length 5 has 5! permutations i.e. 120 permutations in total
How do I print all combinations of a string?
We can count the occurrences of all the characters in the string using a map, then using recursion, all the possible combinations can be printed. And lastly, storing the elements and their counts in two different arrays.
Which algorithm is best for permutation?
The best algorithm for generating permutations depends on the context. The `itertools.permutations()` method in Python or `std::next_permutation` in C++ STL is usually more efficient and easier to use due to their ability to generate permutations one at a time, reducing memory usage.
What is the formula for permutations of a string?
The formula for permutations of a string of 'n' distinct characters is 'n!,' where 'n' represents the number of characters, and '!' denotes the factorial of 'n.'
Conclusion
The string modification includes a wide variety of problems. This article explained one of those problems, finding all the permutations in a string. Basic knowledge of the C++ standard template library and strings is required.