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";
}