Home » Interview coding problems/challenges

Next Permutation

In this article, we are going to how find next permutation (Lexicographically) from a given one? This problem has been featured in interview coding round of Amazon, OYO room, MakeMyTrip, Microsoft.
Submitted by Radib Kar, on February 14, 2019 [Last updated : March 20, 2023]

Problem Description

Given a permutation print permutation just greater than this.

Example

    Permutation:
    1 3 2 5 4

    Output:
    1 3 4 2 5

Solution of Next Permutation

What is permutation?

Permutation is the process of arranging the members of a set into a sequence or order, or, if the set is already ordered, rearranging (reordering) its elements. (Ref. wiki: Permutation)

Example

    Let a set s= {1, 2, 3}

    Then it has six permutations which are
    (1, 2, 3)
    (1, 3, 2)
    (2, 1, 3)
    (2, 3, 1)
    (3, 1, 2)
    (3, 2, 1)
    
    This all are ordered 
    
    Thus the next permutation of (1, 3, 2) is (2, 1, 3) 
    and next of (3, 2, 1) is (1, 2, 3). (Yah! It's cyclic)

Generating Next permutation

This problem has a simple but robust algorithm which handles even repeating occurrences. However for this problem we restrict our discussion to single occurrence of numbers in the permutation.

Pre-requisite:

Input permutation of length n

Algorithm

1.  Find the largest k such that a[k]<a[k+1] , kЄ [0, n-1] //k=-1 initially
2.  IF
    k is not updated (k is -1 still) that means 
    current is the largest permutation (descending order).
    So the next will be the smallest one (ascending order).
    ELSE
3.  Find largest l such that a[k]<a[l]
4.  Swap a[k] and a[l]
5.  Reverse a[k+1] to a[n-1]

Example with Explanation

K initialized to be -1

Example1:
Permutation:
1 3 2 5 4
k=2     //a[k]=2
l=4     //a[l]>a[k] i.e. 4>2
After swapping a[k] and a[l]
Permutation
1 3 4 5 2
Reversing a[k+1] to a[n-1]
1 3 4 2 5 //output 

Example 2:
Permutation:
5 4 3 2 1   //largest in the possible permutations
k=1         //since no such kfound, k is not updated
Sort the current permutation in ascending order
Next Permutation
1 2 3 4 5 //output

C++ implementation for Next Permutation

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

//to print a vector
void print(vector<int> a, int n)
{
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
}

void nextPermutation(vector<int> a, int n)
{
    int k = -1, l, temp;

    //finding largest k s.t. a[k]<a[k+1]
    for (int i = 0; i < n - 1; i++) {
        if (a[i] < a[i + 1])
            k = i;
    }

    //if k not updated sort  and print
    if (k == -1) {
        sort(a.begin(), a.end());
        print(a, n);
        return;
    }

    //find the largest l s.t. a[k]<a[l]
    for (int i = k + 1; i < n; i++) {
        if (a[i] > a[k])
            l = i;
    }

    //swap a[k] and a[l]
    temp = a[k];
    a[k] = a[l];
    a[l] = temp;

    //print upto a[k]
    for (int i = 0; i <= k; i++)
        cout << a[i] << " ";

    //reverse printing for a[k+1] to a[n-1]
    for (int i = n - 1; i > k; i--)
        cout << a[i] << " ";

    cout << endl;
    return;
}

int main()
{
    int n, item;

    cout << "enter length of permutation\n";
    scanf("%d", &n);

    cout << "enter the permutation leaving spaces betweeen two number\n";
    vector<int> a;
    for (int j = 0; j < n; j++) {
        scanf("%d", &item);
        a.push_back(item);
    }

    cout << "Current permutation is:\n";
    print(a, n);
    cout << "next permutation is:\n";
    nextPermutation(a, n);

    return 0;
}

Output

First run:
enter length of permutation
5
enter the permutation leaving spaces betweeen two number
1 3 2 5 4 
Current permutation is:
1 3 2 5 4
next permutation is:
1 3 4 2 5

Second run:
enter length of permutation
5
enter the permutation leaving spaces betweeen two number
5 4 3 2 1
Current permutation is:
5 4 3 2 1
next permutation is:
1 2 3 4 5

---