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

## Leave a Reply