Next Permutation

Saksham Gupta
Last Updated: May 13, 2022

Introduction

Operations on arrays is an important area to master when it comes to programming. Finding the next permutation in an array is one such frequently asked question in coding interviews. You can practice the question at the CodeStudio and return to this blog if you feel stuck. 

Now, permutation simply means a rearrangement of the given elements. But what does the next permutation mean? Next permutation refers to the numerically smallest permutation of a given number that is greater than the given number.

But how will we compare which permutation is greater and which is smaller?

To figure out which of the two permutations is lexicographically smaller, we compare the first elements of each permutation. If they're equal, compare the second, then the third, and so on.

For two permutations, ‘X’ and ‘Y’, if X[i] < Y[i], where ‘i’ is the first index at which the permutations ‘X’ and ‘Y’ differ, then X is lexicographically smaller.

Understanding the Problem

Given a number ‘N’ represented in the form of an array, we have to find the next permutation of the given number. If ‘N’ is itself the largest number, then no such next permutation is possible, so print “NOT POSSIBLE”.

 

Let’s take an example to understand the problem better.

For N = [4,5,2,6,7,3,1], the next greater permutation will be = [4,5,2,7,1,3,6].

 

As 4527136 > 45263731 as well as it is the smallest permutation (among all other permutations) which is greater than the given number.

 

Initial Thoughts

Now before coming to the solutions, let’s look at certain observations first.

  • No next permutation would be possible if the digits are already in descending order—for example, 8521. 
  • We only need to swap the last two digits of the number if all digits are already in ascending order. For example, the next permutation of 4567 will be 4576. 
  • For all other cases, we only need to process the number from the rightmost side (because we need to find the smallest out of all greater numbers).

 

There are many different approaches to solve this problem. Here we will start from the naive one first and then move to the most efficient one.

Brute Force Approach

Algorithm

  • We will start iterating from the end of the given array, ‘NUM’ and look for a pair of indexes (i - 1, i), where NUM[i - 1] < NUM[i].
  • If no such pair exists, the permutation is sorted in reverse order. And, as previously stated, the next permutation for such permutation is not possible.

Assume we've arrived at an index ‘i’ where NUM[i - 1] < NUM[i]. We can simply swap the elements at (i - 1)th and ith positions. However, the resulting permutation may not be the next permutation. As a result, we'll begin looking for the smallest element that is greater than the (i - 1)th element and is on the right side of the (i - 1)th element. Let's say that the element's index is ‘j'.

  • Now after NUM[i] and NUM[j] are swapped. We will get the lexicographically greater permutation of our array, but it may not be the next one in line. But what we can do is we can sort all the elements after (i - 1)th index in the given permutation since the element at the (i - 1)th index in the next permutation is greater than the (i - 1)th element in the given permutation. After sorting, we will get our next permutation.

 

Following is the implementation of the above algorithm in C++.

Program

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

// Function to find the next permutation.
void nextPermutation(int n, vector<int> &num)
{
    // Initializing the variable for marking breakpoint.
    int breakPoint = -1;

    // Looping through the array to find the breakpoint.
    for (int i = num.size() - 1; i > 0; i--)
    {
        if (num[i] > num[i - 1])
        {
            breakPoint = i;
            break;
        }
    }

    // If the breakpoint does not exist.
    if (breakPoint == -1)
    {
        cout << "NOT POSSIBLE\n";
        return;
    }

    // Find the smallest digit on the right side of (breakPoint-1)'th digit which is greater than num[breakPoint-1].
    int j = 0;
    int x = num[breakPoint - 1], smallest = breakPoint;
    for (j = breakPoint + 1; j < n; j++)
        if (num[j] > x && num[j] < num[smallest])
            smallest = j;

    // Swapping num[breakPoint - 1] with the above found smallest digit.
    swap(num[smallest], num[breakPoint - 1]);

    // Sorting the digits after (breakPoint - 1)th index in ascending order.
    sort(num.begin() + breakPoint, num.end());

    // Printing the next permutation of 'NUM'.
    for (int i = 0; i < n; i++)
        cout << num[i] << " ";
}


int main()
{
    // Taking user input.
    int n;
    cin >> n;
    vector<int> num(n, 0);
    for (int i = 0; i < n; i++)
        cin >> num[i];

    // Calling the nextPermutation() function to find the next permutation of the array, 'NUM'.
    nextPermutation(n, num);
}

 

Input

[5,3,4,9,7,6]

3

[1,1,5]

3

[3,2,1]

Output

[5,3,6,4,7,9]

[1,5,1]

NOT POSSIBLE

 

Time Complexity

O(N * logN), where ‘N’ is the size of the given array. 

 

We are using the sort function in the end to sort the right side of the array from the breakpoint. The worst-case would be if the breakpoint is at the 0th index, then the time taken for sorting would be O(N * log(N)). 

 

Space Complexity

O(1).

As we are not using any extra space thus our space complexity is constant.

 

The above implementation costs us O(N * log(N)) time which can easily be improved by making the following changes:

In the last step, we can avoid sorting and simply reverse the digits to get the sorted answer.

You may wonder why this will work? It is because all digits other than the one swapped are linearly sorted in decreasing order. As a result, reversing those digits leads them to be sorted in increasing order.

This will reduce our time complexity to O(N).

Second Approach

Now let’s look at the implementation of the improved algorithm.

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

// Function to find the next permutation.
void nextPermutation(int n, vector<int> &num)
{
    // Initializing the variable for marking breakpoint.
    int breakPoint = -1;

    // Looping through the array to find the breakpoint.
    for (int i = num.size() - 1; i > 0; i--)
    {
        if (num[i] > num[i - 1])
        {
            breakPoint = i;
            break;
        }
    }

    // If breakpoint does not exist.
    if (breakPoint == -1)
    {
        cout << "NOT POSSIBLE\n";
        return;
    }

    // Find the smallest digit on the right side of (breakPoint-1)'th  digit which is greater than numb[breakPoint-1].
    int j = 0;
    int x = num[breakPoint - 1], smallest = breakPoint;
    for (j = breakPoint + 1; j < n; j++)
        if (num[j] > x && num[j] < num[smallest])
            smallest = j;

    // Swapping  number[breakPoint-1] with the above found smallest digit.
    swap(num[smallest], num[breakPoint - 1]);

    // Sorting the digits after (breakPoint - 1)th index in ascending order.
    reverse(num.begin() + breakPoint, num.end());

    // Printing the next permutation of 'NUM'.
    for (int i = 0; i < n; i++)
        cout << num[i] << " ";
}

int main()
{
    // Taking user input.
    int n;
    cin >> n;
    vector<int> num(n, 0);
    for (int i = 0; i < n; i++)
        cin >> num[i];

    // Calling the nextPermutation() function to find the next permutation of the array, 'NUM'.
    nextPermutation(n, num);
}

 

Input

[5,3,4,9,7,6]

3

[1,1,5]

3

[3,2,1]

 

 

 

 

 

Output

[5,3,6,4,7,9]

[1,5,1]

NOT POSSIBLE

 

 

 

Time Complexity

O(N), where ‘N’ is the size of the array.

Since in the worst case, we will traverse the whole permutation twice. So, the overall time complexity will be O(N).

 

Auxiliary Space: O(1)

Since we are not using any extra space, the overall space complexity will be O(1).

Key Takeaways

We learned how we would find the next permutation of a given number. We also saw both the methods possible for the problem and finally reduced the solution to linear complexity. Now, this must be overwhelming for you. But learning never stops, and a good coder should never stop practicing. So now it’s time for you to head over to the best practice platform in the town, CodeStudio, to practice top problems and many more. Till then, Happy Coding!

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think