Q:

# Next Permutation

Given a permutation print permutation just greater than this.

Example:

```    Permutation:
1 3 2 5 4

Output:
1 3 4 2 5```

Algorithm:

```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```