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