lexicographically Next permutation of String or Next greater Permutation of String - UCS - Unleash-Coding-Skills

Thursday, 14 June 2018

lexicographically Next permutation of String or Next greater Permutation of String - UCS


lexicographically Next permutation of String:

Given a word, find a lexicographically greater permutation of it. For example, lexicographically next permutation of “gfg” is “fgg” and next permutation of “acb” is “bac” and for "abbc" is "abcb".
Note: In some cases, the next lexicographically greater word might not exist, e.g,. “aaa” and “edcba”
In C++, there is a specific function that saves us from a lot of code. It’s in the file #include <algorithm>. The function is next_permutation(a.begin(), a.end()). It returns ‘true’ if the function could rearrange the object as a lexicographically greater permutation. Otherwise, the function returns ‘false’.
CPP solution using inbuild next_permutation():

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    string s1 = "acb";
    bool val = next_permutation(s.begin(), s.end());
    if (val == false)
        cout << "No Word Possible" << endl;
    else
        cout << s << endl;
    return 0;
}

Output:



bac


This is a direct solution by using next_permutation in C++ but we can go through next how it is implemented in the best and simplest way in later............


The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.
Let us consider s be the given string input we need to find the lexicographically next permutation of that string.
Approach:
  1. Find the highest index i such that s[i] < s[i+1]. If no such index exists, the permutation is the last permutation.
  2. Find the highest index j > i such that s[j] > s[i]. Such a j must exist, since i+1 is such an index.
  3. Swap s[i] with s[j].
  4. Reverse the order of all of the elements after index i till the last element.

These are the steps you need to follow to implement in our code.

Implemented for the code above in CPP or C++:


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

void nextpermutation(string s)
{
    int i=0,t=s.length(),j=-1,left,right;
// Find the highest index i such that s[i] < s[i+1]. If no such index exists, the permutation is
 //the last permutation.
    for(i=0;i<t-1;i++)
    {
        if(s[i]<s[i+1])
        {
            j=i;
        }
    }
    left=j;
//checking if it highest permutation the repeat 
    if(j==-1)
    {
       cout<<"You will get initial permutataion again after this"<<endl;
    }
    else
    {
//Find the highest index j > i such that s[j] > s[i]. Such a j must exist, since i+1 is such an  index.
        for(i=left+1;i<t;i++)
        {
            if(s[i]>s[left])
            {
                right=i;
            }
        }
//Swap s[i] with s[j].
        swap(s[left],s[right]);
   
    }
//Reverse the order of all of the elements after index 'i' till the last element.
    reverse(s.begin()+left+1,s.end());
    cout<<s<<endl;
}

int main()
{
    string s1="cca";
    nextpermutation(s1);
    return 0;
}

Output:

You will get initial permutataion again after this
acc

If you don't know what reverse() function will do ,you can go through below example.


Input : 1 2 3 4
Output :4 3 2 1
It will simply reverse the array from the indexes that we mentioned in the reverse() function call.

s.begin() -> indicates starting of vector or string or arrray means 0th index.
s.end() -> indicates last element index in the array or string or vector.

So it will reverse the order of elements mentioned in the given indexes.

Happy Coding....................

Vectors in CPP tutorials visit this Links:



Tags:
lexicographically next permutation of string, next permutation, code permutation, next permutation in sequence, permutations, permutation examples, permutations in the array, next largest permutation, a lexicographical arrangement of string, next highest permutation, permutations in an array, largest permutation,hackerrank permutation, maths permutation

No comments:

Post a comment