-
Notifications
You must be signed in to change notification settings - Fork 49
/
Next Permutation Arrays
43 lines (37 loc) · 1.23 KB
/
Next Permutation Arrays
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <vector>
using namespace std;
void nextpermutation(vector<int> &nums)
{
int n = nums.size(), k, l;
for (int k = n - 2; k >= 0; k--)
{
if(nums[k]<nums[k+1])
{
break;
}
}
if(k<0)
{
reverse(nums.begin(), nums.end());
}
else
{
for(int l=n-1;l>k;l--)
{
if(nums[l]>nums[k])
{
break;
}
}
swap(nums[l],nums[k]);
reverse(nums.begin()+k+1,nums.end());
}
}
/*
Approach :
Step 1: Linearly traverse array from backward such that ith index value of the array is less than (i+1)th index value. Store that index in a variable.
Step 2: If the index value received from step 1 is less than 0. This means the given input array is the largest lexicographical permutation. Hence, we will reverse the input array to get the minimum or starting permutation. Linearly traverse array from backward. Find an index that has a value greater than the previously found index. Store index is another variable.
Step 3: Swap values present in indices found in the above two steps.
Step 4: Reverse array from index+1 where the index is found at step 1 till the end of the array
*/