Prerequisite : - Sorting.
Problem :- Given two integers N and M, the length of the permutations and the number of different permutations.
Find the next greater permutation for each given permutation.
Explanation :-
Next Greater permutations :- In the context of permutations, a permutation is an arrangement of elements. The “next greater permutation” refers to the permutation that comes immediately after the current permutation in lexicographical (dictionary) order.
For example, let’s consider the permutation [1, 2, 3]. The next greater permutation would be [1, 3, 2]. If you list all permutations of [1, 2, 3] in lexicographical order, you would get:
[1, 2, 3]
[1, 3, 2] ← Next greater permutation
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
So, given a particular permutation, finding the next greater permutation involves determining the arrangement that comes just after it when ordered lexicographically.
Steps for finding next greater permutation : -
Given permutation :- [8,9,7,4,6,5,3,2,1]
Pivot point - moving from right to left the first decreasing element we find is our pivot point. In the given pattern 4 is our pivot point.
Find the pivot point.
After the pivot point is found, Find the successor of pivot in suffix(The element that is the next greater one to the pivot point, present on the right side of the pivot, is called the successor. In the given example, 5 is the successor. ).
Swap the pivot and successor
Minimize the suffix by sorting the elements(Replacing the pivot point with the successor makes our permutation greater than the initial number. However, to ensure there is no number in between these two permutations, we need to sort the right side of the pivot point).
C++ Solution : -
#include <bits/stdc++.h>
using namespace std;
void nextPermutation(vector<int>& arr)
{
int n = arr.size(), i, j;
// Find for the pivot element.
// A pivot is the first element from
// end of sequenc ewhich doesn't follow
// property of non-increasing suffix
for (i = n - 2; i >= 0; i--) {
if (arr[i] < arr[i + 1]) {
break;
}
}
// Check if pivot is not found
if (i < 0) {
reverse(arr.begin(), arr.end());
}
// if pivot is found
else {
// Find for the successor of pivot in suffix
for (j = n - 1; j > i; j--) {
if (arr[j] > arr[i]) {
break;
}
}
// Swap the pivot and successor
swap(arr[i], arr[j]);
// Minimise the suffix part
reverse(arr.begin() + i + 1, arr.end());
}
}
int main() {
int n,m;
cin>>n>>m;
for(int i=0; i<m; i++){
vector<int>v1(n);
for(int j=0; j<n; j++){
cin>>v1[j];
}
nextPermutation(v1);
for(auto e:v1){
cout<<e<<" ";
}
cout<<"\n";
}
}