All permutations of a string using next_permutation in C++

By mahima mahendru

Here we will be discussing how to generate all permutations of a string using an STL function next_permutation() in C++.

Given a string s, our task is to generate all possible strings using all the characters in it, that is all the strings have the same characteristics (length, frequency of each character, etc)  but different arrangements of the characters.

->In C++, there is a specific function that saves us from a lot of code. It’s in the file #include.

->The function is next_permutation(s.begin(), s.end()) which returns ‘true’ if the function could rearrange the string as a lexicographically greater permutation. Otherwise, the function returns ‘false’.

->Example: The  next_permutation function when used on the string say "PQR", would give the output as "QPR" which is lexicographically the next larger permutation. We can use this function to generate all the string permutations.

PROCEDURE:

1. First sort the string using STL function sort() which ensures that the given string is lexicographically smallest.

2. Use a vector of strings to store all the string permutations.

3. Run a do-while loop until next_permutation returns false.

4. Print the number of strings generated which is given by the size of the vector and all the strings stored in the vector.

Below is C++ implementation.

#include
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
int main()
{
   
        string s;
        cin>>s;
        
        vectorv;
        
        sort(s.begin(),s.end());      //GIVES THE LEXIOGRAPHICALLY SMALLEST PERMUATATION
        
        do{
            
            v.push_back(s);
            
        }while(next_permutation(s.begin(),s.end()));
        
        //PRINT THE NUMBER OF STRINGS
         cout<<"TOTAL NUMBER OF PERMUTATIONS ARE:  "<<v.size()<<endl;
         
         //PRINT THE PERMUTATIONS
         
         for(int i=0;i<v.size();i++)
             cout<<v[i]<<endl;
       
        
}

LET'S SEE THE OUTPUT FOR STRING "ADCB"