Lexicographically next permutation in C++

In this tutorial, we going to find the next permutation of a string in lexicographically (dictionary order) in C++. The basic need for this is when doing mathematical problems requiring the premutation/rearrangement of digits in a number.

The ultimate library <algorithm>

This library provides us with built-in methods and tricks for many problems such as heap operations, merge operations, sorting operations, binary search operations, and many more.

The syntax to import this library :

#include <algorithm>

This library also includes the next permutation(start iterator, end iterator) which is used to find the next permutation in this sequence of range [start, end) in dictionary order.

The permutation is the rearrangement of elements in the sequence which leads to distinct sequences.

The number of permutations with n total elements  = (n)!;

In the case of “abcadebgbx” : permutations = (10!)/((2!)*(3!)) ,   dividing by 2 ! because ‘a’ repeats two times and ‘b’ repeats 3 times.

Let us see some use of it on the array of 3 numbers.

int nums[] = { 2, 3, 4};
do{
    for(int i = 0; i < 3; i++)
        cout<<nums[i]<<" ";
    cout<<endl;
}while(next_permutation(nums,nums+3));

Output : 
2 3 4
2 4 3
3 2 4
3 4 2
4 2 3
4 3 2

Program: Lexicographically next permutation in C++

Let’s see the implementation for a string permutation.

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

int main() {
    string p;
    getline(cin, p);
    sort(p.begin(), p.end());
    
    if(next_permutation(p.begin(),p.end())){
        cout<<p<<endl;
    }
    else{
        cout<<"No word possible"<<endl;
    }
}

Input  : abcde

Output : abced

This function can be applied to any sequence of primitive data structures and can be useful when searching a name or a number using the brute force method. This technique is used by many password crackers available out there.

We can also do this program without using the built-in method but that will be inefficient as compared to this code.