Lexicographically Next Permutation in C++

In this tutorial, we'll look at how to use C++ to generate the lexicographically next permutation of a string. The lexicographically next permutation is the larger permutation. "ACB," for example, will be followed by "BAC." The lexicographically next permutation is not present in some cases, such as "BBB" or "DCBA."

Lexicographical Order

When all the permutations of a word are sorted in a dictionary, the resulting order of words is known as lexicographical order. Simply said, it is the one with all of its elements sorted ascending, whereas the largest has all of its elements sorted descending. It is nothing more than the greatest permutation of it lexicographically.

a b c d e f g h I j k l m n o p q r s t u v w x y z as a guide.

The next lexicographic permutation of "jtp" is "pjt."

Keep in Mind: In some circumstances, such as "aaa" and "edcba," the next lexicographically bigger word may not exist.

In C++, there is a function that relieves us from writing a huge amount of code. It's in the #include<algorithm> file. next_permutation(a.begin(), a.end()) is the function.

If the function can rearrange the item into a lexicographically greater permutation, it returns 'true.' If not, the method returns 'false.'

Example:

C++ Program

// A CPP code that displays the next lexicographically greater permutation of a word.
#include <algorithm>
#include <iostream>
using namespace std;


int main ()
{
	string strng = { "jtp" };
	bool value
		= next_permutation ( strng.begin (),
						strng.end () );
	if ( value == false )
		cout << "No Word Possible"
			<< endl;
	else
		cout << strng << endl;
	return 0;
}

Output:

pjt

The identical code can also be written without the use of STL. The code for this is shown below.

The following facts Illustrate the Concept:

1. The next permutation does not exist in a specific order arranged in descending order. The following permutation, for example, does not exist for "edcba."
2. These steps can be used for a specific order that is not arranged in descending order, such as "abedc."
   • From the right, find the first item that does not follow the ascending order. In "abedc," for example, the character 'b' doesn't at all pursue the ascending order.
   • Replace the detected character with the nearest greater (or smallest greater) element on its right side. In the case of "abedc," the nearest bigger element is 'c'. After exchanging the letters 'b' and 'c,' the string becomes "acedb."
   • Following swapping, turn the string after the character detected in step a. We get "acbde" after reversing the substring "edb" of "acedb." This is the desired next permutation.
     Steps b) and c) performance enhancements
   • We utilise binary search to discover the nearest bigger element because the sequence is arranged in decreasing order.
   • Because the sequence is arranged in decreasing order, one utilise binary search to locate the nearest greater element.

C++ Program

// CPP code that displays the next lexicographically greater permutation of a word.
#include <iostream>
using namespace std;


void swap ( char* x, char* y )
{
	if ( *x == *y )
		return;
	*x ^= *y;
	*y ^= *x;
	*x ^= *y;
}
void revs ( string& strng, int a, int b )
{
	while ( a < b )
		swap ( &strng [a++], &strng [b--] );
}
int binarysearch ( string& strng, int a, int b, int key )
{
	int index = -1;
	while ( a <= b ) {
		int mid = a + ( b - a ) / 2;
		if ( strng [mid] <= key )
			b = mid - 1;
		else {
			a = mid + 1;
			if ( index == -1 || strng [index] >= strng [mid] )
				index = mid;
		}
	}
	return index;
}


bool nextpermutation ( string& strng )
{
	int len = strng.length(), i = len - 2;
	while ( i >= 0 && strng [i] >= strng [i + 1] )
		--i;
	if ( i < 0 )
		return false;
	else {
		int index = binarysearch ( strng, i + 1, len - 1, strng[i] );
		swap ( &strng [i], &strng [index] );
		revs ( strng, i + 1, len - 1 );
		return true;
	}
}
int main ()
{
	string strng = { "jtp" };
	bool value = nextpermutation (strng);
	if ( value == false )
		cout << "No Word Possible" << endl;
	else
		cout << strng << endl;
	return 0;
}

Output:

pjt

Time Complexity:

• The initial step of next_permutation tends to take O(n) time in the worst-case scenario.
• The binary search tends to take O(log n) time to complete.
• The reverse tends to take O(n) time.

O(n) is the overall temporal complexity, here n is the string's length.

Space Complexity:

As no extra space is used, Space complexity will be O(1).