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; }

#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<t1;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:
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