Advanced C++ Programming and Algorithms

Print all Permutations of given String: using C++

Board Infinity
Board Infinity
Print all Permutations of given String: using C++

    OOPs (Object Oriented Programming) in C++

    A Quick Guide to Encapsulation in C++

    OOPs Abstraction in C++

    OOPS Polymorphism with C++

    Multiple Inheritance in C++

    Virtual Base Class in C++

    How to Perform Insertion Sort in C++?

    Counting Sort Algorithm: Using C++

    Bucket Sort Algorithm with C++

    Implementing Binary Search in C++

    Print all Permutations of given String: using C++

    Sliding Window Problem – C++ Implementation

    Implement Tower of Hanoi using C++

    Rabin Karp Algorithm: C++ Implementation

    Job Sequencing Problem with C++

    Biconnected Graph Algorithm with C++

    Hamiltonian Path Algorithm with C++

What do permutations mean?

Permutation is defined as "various arrangements produced out of a certain number of things by taking some or all of them."

For instance, the permutation of the three letters abc is: ab, ba, bc, cb, ac, ca.

In coding contests and various placement exams, strings are frequently asked about. We will discuss "Permutations in String," one of the most frequently asked questions based on strings, in this post.

Problem Proposition:

You are given a string of lowercase letters, "str," to enter. Return every permutation in the string, in any order.

Sample Input :

abc

Sample Output:

cab, cba, bac, acb, and abc

Solution Method :

The permutations of a string can be printed using a variety of algorithms and methods.

Approach-1 Using the Backtrack

A backtracking method attempts to create a solution gradually, one step at a time, and discards any alternatives that do not meet the criteria of the problem at any point in time. Backtracking is a recursive problem-solving strategy.

Backtracking is the best method for printing every variation as a string.

Algorithm

  • We'll create a function called generatePermutaionsHelper in the algorithm (Str, l, r). The permutations of the substring produced by this function start at index "l" and end at index "r." Invoking the generatePermutaionsHelper method mentioned above (Str, l, r).
  • A new permutation is discovered if "l" equals "r." Put this string in the list of "ans."
  • If not, keep repeating the string from "l" to "r."
  • Assign the current index to "i."
  • To correct the "ith" character on the index "l," swap Str[l] and Str[i].
  • To obtain the permutation of the remaining characters, call generatePermutaionsHelper(Str, l + 1, r).
  • Go back and switch Str[l] and Str[i] once again.

By the time we're done, the list "ans" will include every possible combination of the supplied string. We must sort the list in order to get the permutations in lexicographically increasing order.

Implementation of Approach-1

#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 permutations of a 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);
   
    //Lexographically increasing order
    sort(ans.begin(),ans.end());
    for (int i = 0; i < ans.size(); i++)
    {
        cout<<ans[i]<<endl;
    }
    return 0;
       
}

Output:

aac
aac
aca
aca
caa
caa

write your code here: Coding Playground

Time complexity

This method's temporal complexity, where N is the string's length, is O(N!).

Reason :

The reason is that we are randomly creating each of the n! permutations. Thus, it takes O(N!) time to create every variant of a string. Additionally, we are sorting the O(N!)-dimensional "ans" list, which will take O(log(N!)) time.

A final time complexity of O(log(N!) + N!) O(N!) is obtained.

Space Complexity

This method's temporal complexity is O(N! ), where N is the length of the supplied string.

Reason:

The recursive function use the O(N) recursion stack as the cause. Additionally, we keep the permutations in an O(N!)-sized list. The total space complexity is therefore O(N + N!) O(N!).

Drawbacks of the aforementioned strategy

The aforementioned strategy works well when each character in a string is unique. However, this method will display duplicate permutations if the string contains repeated characters, as you can see in the example above. To handle the aforementioned test scenario, there is a version of the backtracking strategy (discussed below).

Approach 2: Backtracking to Prevent Repetition

To accomplish this, we merely make a small change to the code above. We must make sure that no character is used twice for the prefix before calling the subproblems.

In essence, this means that only unique characters should be used at each level of the recursion. How then do we approach doing that?

To account for the characters utilized, we can achieve this by making a boolean array of size (26).

  • If the character is not utilized, only then will the recursive function be called.
  • A character can only be chosen once. The distinct selection criteria is therefore satisfied.

The permutations produced in the output will be in lexical order, which is a huge benefit of choosing the input string characters in this way (dictionary order). This makes verifying the program's accuracy simple.

Implementation of Approach-2

#include<bits/stdc++.h>
using namespace std;

void printPermutations(string str, string ans)
    {
 
        // If string is empty
        if (str.length() == 0)
        {
            cout<<ans<<endl;
            return;
        }
 
        // Make a boolean array of size '26' which stores true
        // at the position in which alphabet is being used
       
        bool alpha[26];
 
        for (int i = 0; i < str.length(); i++) {
 
            char ch = str.at(i);
 
            // the string after excluding the ith character
            string ros;
            ros = str.substr(0, i) + str.substr(i + 1);
 
            // If the character has not been used
            // then a recursive call will take place.
            // Otherwise, there will be no recursive
            // call
            if (alpha[ch - 'a'] == false)
                printPermutations(ros, ans + ch);
            alpha[ch - 'a'] = true;
        }
    }
int main()
{
    string s = "aabc";
    string ans = "";

    //Empty Input String
    if(s.length()==0)
    {
        cout<<"No Permutations Possible!!";
    }
    else
        printPermutations(s, ans);
    return 0;
}

Output :

aabc

aacb

write your code here: Coding Playground

Complexity in Time and Space

The above method has the same level of temporal complexity.

Have you already observed a difference in the outputs of two codes despite the identical input string "aac"?

Output 1 : displays repeated string permutations.

Output 2 :Yes, there are no repeating string variations.

Approach-3 :Utilizing the next permutation method of the C++ library.

The next permutation function is one of many available to change strings in the standard C++ library. If it is possible to rearrange the text in a more lexicographically extensive permutation, the next permutation function returns true. Otherwise, false is returned.

As a result, this approach likewise stays away from string repetitions.

Implementation of Approach-3

#include <bits/stdc++.h>
using namespace std;
// Function to print permutations of a string
void printPermutation(string str)
{
    // Sort the string in ascending order
    sort(str.begin(), str.end());
    // Keep printing next permutation
    do
    {
      cout << str << endl;
    }
    while (next_permutation(str.begin(), str.end()));
}
int main()
{
    string str = "aabc";
    string ans = "";

    //Empty Input String
    if(str.length()==0)
    {
        cout<<"No Permutations Possible!!";
    }
    else
        printPermutation(str);
    return 0;
}

Output :

aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa

write your code here: Coding Playground

Time complexity

This method's time complexity is O(N * N!).

Reason:

The next permutation function's temporal complexity is O (N). N! calls are made to this procedure. The overall temporal complexity is therefore O(N * N!).

Space Complexity

This method has an O(N!) space complexity, where N is the length of the supplied string.

Reason:

This method uses no more space. It has continuous spatial complexity as a result.