Problem Statement

Given a sequence of elements, the next lexicographically greater permutation is the rearrangement of these elements that is greater in value that the current permutation but smallest among all possible permutations greater than the current one. If no such permutation exists, the arrangement is modified to the first permutation in lexicographic order.

Examples

Example 1:

Input: arr[] = {1, 3, 2}

Output: arr[] = {2, 1, 3}

Explanation: All permutations of {1,2,3} are {{1,2,3} , {1,3,2}, {2,13} , {2,3,1} , {3,1,2} , {3,2,1}}. So, the next permutation just after {1,3,2} is {2,1,3}.

Different Approaches

1 Brute Force Approach

Intuition:

• Generate all possible permutations of the sequence and find the next greater one.

2 Using in-built function

C++ provides an in-built function called next_permutation() which directly returns the lexicographically next greater permutation of the input.

Code:

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
    int arr[] = {1,3,2};
    
    next_permutation(arr,arr+3);//using in-built function of C++
    
    cout<<arr[0]<<" "<<arr[1]<<" "<<arr[2];
    
    return 0;
}

3