Tutorialspoint.dev

Lexicographically next permutation in C++

Given a word, find lexicographically greater permutation of it. For example, lexicographically next permutation of “gfg” is “ggf” and next permutation of “acb” is “bac”.

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’.

Let us look at the code snippet here :

// Find the next lexicographically greater permutation of a word
#include <iostream>
#include <algorithm>
  
using namespace std;
  
int main()
{
    string s = {"gfg"};
    bool val = next_permutation(s.begin(), s.end());
    if (val == false)
        cout << "No Word Possible" << endl;
    else
        cout << s << endl;
    return 0;
}

Output:



ggf

The same program can also be implemented without using STL.Below is the code snippet for the same:

// Find the next lexicographically greater permutation of a word

#include <iostream>
  
using namespace std;
  
void swap(char *a,char *b)
{
    if( *a == *b )
        return;
    *a^=*b;
    *b^=*a;
    *a^=*b;
}
void rev(string& s,int l,int r)
{
    while(l<r)
        swap(&s[l++],&s[r--]);
}
  
int bsearch (string& s,int l,int r,int key)
{
    int index = -1;
    while(l<=r)
    {
        int mid = l+(r-l)/2;
        if(s[mid]<=key)
            r=mid-1;
        else
        {
            l=mid+1;
            if(index = -1 || s[index]<=s[mid])
                index = mid;
        }
    }
return index;
}
  
bool nextpermutation(string& s)
{
    int len = s.length(), i=len-2;
    while(i>=0 && s[i]>=s[i+1])
       --i;
    if(i<0)
        return false;
    else
    {
        int index=bsearch(s,i+1,len-1,s[i]);
        swap(&s[i],&s[index]);
        rev(s,i+1,len-1);
        return true;
    }
}
  
// Driver code
int main ()
{
    string s = {"gfg"};
    bool val = nextpermutation(s);
    if (val == false)
        cout << "No Word Possible" << endl;
    else
        cout << s << endl;
    return 0;
}
// This code is contributed by Mysterious Mind

Output:

ggf

Reference: http://www.cplusplus.com/reference/algorithm/next_permutation/

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter