 # Find next permutation

Given a permutation of numbers in the form of an array ` arr `, find the immediate next lexicographically greater permutation. If the next lexicographically greater permutation is not possible, print the permutation as is.

#### Example Test Cases

##### Sample Test Case 1

Input Array: ` [1, 2, 3 ] `
Expected Output: ` [1, 3, 2 ] `
Explanation: The next lexicographically greater permutation is [1, 3, 2]

##### Sample Test Case 2

Input Linked List: ` [4, 3, 7, 6 ] `
Expected Output: ` [4, 6, 3, 7 ] `

#### Solution

To find the next lexicographic permutation of these numbers, we would need to swap two numbers from index ` i ` and index ` j ` such that ` j > i ` and ` arr[j] > arr[i] `.
To find the just next lexicographic permutation, we would want to increase ` i ` as much as possible and minimize ` arr[j] ` for example, in the sample test case 2 ` [4, 3, 7, 6 ] `, we could have swapped element at position ` i = 0 ` with element at position ` j = 3 ` which would have given us permutation ` [6, 3, 7, 4] `
Clearly this is not the optimal solution. Therefore, we will swap element at position ` i = 1 ` with element at position ` j = 3 ` (to maximize ` i ` and minimize ` arr[j] ` ). To further minimize the permutation we will sort the array from position ` (i + 1 ` onwards, which will give us the desired answer.
See the below code for implementation.

### Implementation

```#include <bits/stdc++.h>
using namespace std;

// Finds the smallest element which is located after position l and is larger than arr[l];
int findNextLargerElement(vector& arr, int l) {
int soFar = -1;
for(int j = l + 1; j < arr.size(); j++) {
if (arr[j] > arr[l]) {
if (soFar == -1) {
soFar = j;
}
else if (arr[j] < arr[soFar]) {
soFar = j;
}
}
}
return soFar;
}

void swap(vector& arr, int i , int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

void nextPermutation(vector& arr) {
bool flag = false;
int pos = -1;
int minSoFar = arr.size() - 1;
int maxSoFar = arr.size() - 1;
// loop to find the position which should be swapped.
for(int i = arr.size() - 2; i >= 0 && !flag; i--) {
if (arr[i] < arr[minSoFar]) {
swap(arr, i, minSoFar);
pos = i + 1;
flag = true;
}
else if (arr[i] >= arr[minSoFar] && arr[i] < arr[maxSoFar]) {
int mi = findNextLargerElement(arr, i);
swap(arr, i, mi);
pos = i + 1;
flag = true;
}
if (arr[i] < arr[minSoFar]) {
minSoFar = i;
}
if (arr[i] > arr[maxSoFar]) {
maxSoFar = i;
}
}
if (!flag) {
sort(arr.begin(), arr.end());
}
else {
sort(arr.begin() + pos, arr.end());
}
}

int main() {
vector arr = { 4, 3, 7, 6 };
nextPermutation(arr);
cout << "Next permutation is \n";
for(int i = 0; i < arr.size(); i++) {
cout << arr[i] << " ";
}
cout << "\n";
}```
Scroll to Top