3

Lexicographically largest permutation transformation

 11 months ago
source link: https://www.geeksforgeeks.org/lexicographically-largest-permutation-transformation/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Lexicographically largest permutation transformation

Given an arr[] of size n, the task is to find the lexicographically largest permutation from the given permutation by performing the following operations exactly once where you will choose two integers l and r and reverse the subarray [l, r] and swap [1, l-1] with [r+1, n].

Examples:

Input: arr[] = { 2, 3, 1, 5, 4}
Output: {5, 4, 1, 3, 2 }
Explanation: we will choose l = 2 and r =3, then after performing operation, the permutation will be {5, 4, 3, 1, 2 }

Input: arr[] = { 6, 1,  2, 3, 5, 4 }
Output: {5, 4, 3, 6, 1, 2 }
Explanation: we will choose l = 4 and r  = 4, then after performing the operation, the permutation will be {5, 4, 3, 6, 1, 2}

Approach: To solve the problem follow the below idea:

There will be two cases: 

  • If arr[0] = n  . if arr[1] == n-1, then choose l = 0 and  r = 0. Else let arr[j] = n-1, then choose l = j-1 and  r = j-19(0-based indexing ) .
  • If arr[0] != n . let arr[j] = n, then iterate while loop from j-1 to 0 till arr[i] > arr[0]  and decrease i by 1, then our l will be i and r will be j.

Below is the implementation of the above approach:

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;

// Function to print new lexographically
// largest permutation from a given
// permuatation by performing exactly
// one operation
void lexogra_permutation(int* arr, int n)
{
    int j, k;

    // New lexographically largest
    // permutation
    vector<int> permu;

    // If first element is equal to n
    if (arr[0] == n) {

        // If second element equal to n
        if (arr[1] == n - 1) {

            // Inserting subarray[1, n-1]
            // in permu
            for (int i = 1; i < n; i++) {
                permu.push_back(arr[i]);
            }

            // Inserting subarray[0, 0] in
            // permu
            permu.push_back(arr[0]);
        }
        else {

            // Find value of j such that
            // a[j] = n
            for (int i = 1; i < n; i++) {

                // if j found, then break
                if (arr[i] == n - 1) {
                    j = i;
                    break;
                }
            }

            // Inserting subarray[j, n-1]
            // in permu
            for (int i = j; i < n; i++) {
                permu.push_back(arr[i]);
            }

            // Inserting subarray[j-1, j-1]
            // in permu
            permu.push_back(arr[j - 1]);

            // Inserting subarray[0, j-1]
            // in permu
            for (int i = 0; i < j - 1; i++) {
                permu.push_back(arr[i]);
            }
        }
    }

    // If first element isn't
    // equal to n
    else {

        for (int i = 0; i < n; i++) {

            // If j found, then break
            if (arr[i] == n) {
                j = i;
                break;
            }
        }
        k = j - 2;

        // Till k is >= 0 & a[k] greater
        // than arr[0]
        while (k >= 0 && arr[k] > arr[0]) {
            if (arr[k - 1] > arr[0] && k - 1 >= 0) {
                k--;
            }
            else {
                break;
            }
        }

        // Inserting subarray[j, n-1] in
        // permu
        for (int i = j; i < n; i++) {
            permu.push_back(arr[i]);
        }

        // Inserting reverse of
        // subarray[k, j-1] in permu
        for (int i = j - 1; i >= k; i--) {
            permu.push_back(arr[i]);
        }

        // Inserting subarray[0, k-1]
        // in permu
        for (int i = 0; i < k; i++) {
            permu.push_back(arr[i]);
        }
    }

    // Lexographically largest
    // new permutation
    for (int i = 0; i < permu.size(); i++) {
        cout << permu[i] << " ";
    }
}

// Driver code
int main()
{
    int arr[] = { 2, 3, 1, 5, 4 };
    int n = sizeof(arr) / sizeof(int);

    // Function call
    lexogra_permutation(arr, n);

    return 0;
}
Output
5 4 1 3 2

Time Complexity: O(N)
Auxiliary Space: O(N)


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK