next permutation in c++
INTRODUCTION
In this tutorial, we are going to earn about next_permutation in C++. this is a keyword in C++ which is used to list all the permutations of the given array elements in ascending order. This keyword is used to return all the possible permutations of the given set of numbers in the ascending 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 next_permutations is.
Return_value next_permutation ( first_element,
Last_element)This is the syntax of the next_permutations in C++. observing the syntax of the method, we see
Return_value: it determines the return type of the next permutation. If the next permutation is greater 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 lexicographic order of the permutations.
Parameters: these are the parameters which define the range of the set of elements. The first_element and last_element are the elements which are traversed first and last in the set of elements respectively. According to the set, permutations will be returned according to their lexicographic order( returned permutation should be greater than the previous permutation ).
Applications:
The main application of the next_permutation is to find the next permutation which is greater than the previous one, by following the lexicographic order of the elements.
Let’s look at the sample program implementing next_permutation.
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
int arr[] = { 1, 2, 3 };
sort(arr, arr + 3);
cout << "possible permutations of elements are:\n";
do {
cout << arr[0] << " " << arr[1] << " " << arr[2] << "\n";
} while (next_permutation(arr, arr + 3));
return 0;
}
The output of the program is.
In the above program, we have passed the next_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, the next_permutation function is passed over the sorted set of elements and do while the loop is being 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 are not sorted, that is the elements of the set don’t follow the 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 greater 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 (next_permutation(arr, arr + 3));
return 0;
}
The output of the program is.
In the above set of elements, the first parameter of the next_permutation function is 2, so the code returned the possible permutations which are only greater, following the lexicographic order.
CONCLUSION:
That’s it from this tutorial. We have learned about next_permutation in C++. Happy Coding!
