INTRODUCTION
In this tutorial, we are going to earn about prev_permutation in C++. this is a keyword in C++ which is used to list all the permutations of the given array elements in descending order. This keyword is used to return all the possible permutations of the given set of numbers in the descending order of their value. The time complexity of the code is O(n*n!) as it returns all the possible permutations of n numbers which are factorial of the N numbers.
The syntax of the prev_permutations is.
Return_value prev_permutation ( first_element,
Last_element);This is the syntax of the prev_permutations in C++. observing the syntax of the method, we see
Return_value:
it determines the return type of the prev permutation. If the permutation is lesser than the previous one, then it returns the permutation as it is true. Otherwise, no permutation will be returned as it was not following the reverse lexicographic order of the permutations.
Parameters:
These are the parameters that define the range of the set of elements. The first_element and last_element are the elements that are traversed first and last in the set of elements respectively. According to the set, permutations will be returned according to their reverse lexicographic order( returned permutation should be lesser than the previous permutation ).
Applications:
The main application of the prev_permutation is to find the next permutation which is lesser than the previous one, by following the reverse lexicographic order of the elements.
Let’s look at the sample program implementing prev_permutation.
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
int arr[] = { 1, 2, 3 };
sort(arr, arr + 3);
reverse(arr, arr + 3);
cout << "possible permutations of elements are:\n";
do {
cout << arr[0] << " " << arr[1] << " " << arr[2] << "\n";
} while (prev_permutation(arr, arr + 3));
return 0;
}
The output of the program is.
In the above program, we have passed the prev_permutation function over the set of elements. Before passing the function, we sorted the set of elements in order to return each possible permutation of the set of elements. After sorting the elements, we used the reverse() function in order to reverse the elements. After reversing the elements, the prev_permutation function is passed over the reverse sorted set of elements and done while the loop is initialized to return the possible permutations of the set of elements. So as you see the output of the program, the code returned the possible set of the permutations of the set of elements.
NOTE: if the elements don’t follow the reverse lexicographic order, the function will return the possible permutations according to the first element of the set, meaning that the permutations will be returned which are only lesser than the first element of the set.
Let’s understand it by seeing the below program.
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
int arr[] = { 2, 1, 3 };
cout << "possible permutations of elements are:\n";
do {
cout << arr[0] << " " << arr[1] << " " << arr[2] << "\n";
} while (prev_permutation(arr, arr + 3));
return 0;
}
The output of the program is.
In the above set of elements, the first parameter of the prev_permutation function is 2, so the code returned the possible permutations which are only lesser, following the reverse lexicographic order.
CONCLUSION:
That’s it from this tutorial. We have learned about prev_permutation in C++.
Happy Coding!
