1. Find the largest k such that a[k]<a[k+1] , kЄ [0, n-1] //k=-1 initially
2. IF
k is not updated (k is -1 still) that means
current is the largest permutation (descending order).
So the next will be the smallest one (ascending order).
ELSE
3. Find largest l such that a[k]<a[l]
4. Swap a[k] and a[l]
5. Reverse a[k+1] to a[n-1]
Example with Explanation:
K initialized to be -1
Example1:
Permutation:
1 3 2 5 4
k=2 //a[k]=2
l=4 //a[l]>a[k] i.e. 4>2
After swapping a[k] and a[l]
Permutation
1 3 4 5 2
Reversing a[k+1] to a[n-1]
1 3 4 2 5 //output
Example 2:
Permutation:
5 4 3 2 1 //largest in the possible permutations
k=1 //since no such kfound, k is not updated
Sort the current permutation in ascending order
Next Permutation
1 2 3 4 5 //output
C++ implementation
#include <bits/stdc++.h>
using namespace std;
//to print a vector
void print(vector<int> a,int n){
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
void nextPermutation(vector<int> a,int n){
int k=-1,l,temp;
//finding largest k s.t. a[k]<a[k+1]
for(int i=0;i<n-1;i++){
if(a[i]<a[i+1])
k=i;
}
//if k not updated sort and print
if(k==-1){
sort(a.begin(),a.end());
print(a,n);
return;
}
//find the largest l s.t. a[k]<a[l]
for(int i=k+1;i<n;i++){
if(a[i]>a[k])
l=i;
}
//swap a[k] and a[l]
temp=a[k];
a[k]=a[l];
a[l]=temp;
//print upto a[k]
for(int i=0;i<=k;i++)
cout<<a[i]<<" ";
//reverse printing for a[k+1] to a[n-1]
for(int i=n-1;i>k;i--)
cout<<a[i]<<" ";
cout<<endl;
return;
}
int main(){
int n,item;
cout<<"enter length of permutation\n";
scanf("%d",&n);
cout<<"enter the permutation leaving spaces betweeen two number\n";
vector<int> a;
for(int j=0;j<n;j++){
scanf("%d",&item);
a.push_back(item);
}
cout<<"Current permutation is:\n";
print(a,n);
cout<<"next permutation is:\n";
nextPermutation(a,n);
return 0;
}
Output
First run:
enter length of permutation
5
enter the permutation leaving spaces betweeen two number
1 3 2 5 4
Current permutation is:
1 3 2 5 4
next permutation is:
1 3 4 2 5
Second run:
enter length of permutation
5
enter the permutation leaving spaces betweeen two number
5 4 3 2 1
Current permutation is:
5 4 3 2 1
next permutation is:
1 2 3 4 5
Algorithm:
Example with Explanation:
C++ implementation
Output
need an explanation for this answer? contact us directly to get an explanation for this answer