Next Permutation and Previous Permutation in C++

In this article we will learn the ways to find the next and previous permutation of the given arrangement.

Next and Previous Permutation

Given an array of numbers, rearrange the array such that the rearranged array becomes lexicographically next greater and previous smaller permutation of the initial given array.

Examples of Next Greater Permutation

  1. [1,2,3] will have the next greater permutation [1,3,2].
  2. [1,3,2] will have the next greater permutation [2,1,3].
  3. [1,2,3,6,5,4] will have the next greater permutation [1,2,4,3,5,6].

Examples of Previous Smaller Permutation

  1. [3,2,1] will have the previous smaller permutation [3,1,2].
  2. [3,1,2] will have the previous smaller permutation [2,3,1].
  3. [1,9,4,6,7] will have the previous smaller permutation [1,7,4,6,9].

Brute Force Approach for finding Previous and Next Permutations in C++

In this approach we will find all the possible arrangements of the given array and then we will find the arrangement which is smallest but greater than given arrangement as Next Greater Permutation and largest but smaller than given arrangement as Previous Smaller Permutation using recursion.

Time Complexity-O(N!XN)

Where N is the number of elements in the given array.
Making the total number will require time complexity O(N!XN) and there will be a total N! Arrangement possible with the N number of elements so searching time will be O(N!).

Space complexity- O(1).

We don’t require any additional space for this.

Next Permutation in C++ Using Inbuilt Function

We can use the inbuilt function in C++ called next_permutation() which will directly return the lexicographically next greater permutation in C++.

Code for Next Permutation in C++ Using Inbuilt Function

#include
using namespace std;
int main() {
    int arr[] = {1,3,2};    
    next_permutation(arr,arr+3);
//using in-built function of C++    
    cout<
						 

Solution 3 for Next Permutation in C++

Intuition

Observe the following case:
Given Array Next Greater Permutation
1, 2, 3 1, 3, 2
2, 1, 3 2, 3, 1
1, 3, 2 2, 1, 3
3, 2, 1 Not Possible

We can observe that Next permutation is possible unless the arrangement is sorted in descending order.
Also we can see that after a certain index the Next Permutation is in sorted index in ascending order.
We have to find the largest index i such that a[i] < a[i+1].Here a[i+1] is the starting point from which an increasing sequence starts until the end of the array.
After finding the index i, we will swap the value at i index with a value which is smallest but greater than a[i] which is present at index j where i < j< size(array).

Approach to Find Next Permutation

  1. Linearly traverse through the array from the backwards and find the index i such that a[i] < a[i+1].
  2. If i value is less than zero, return the given array in reverse order, as there is no lexicographically next greater permutation is possible as the array is sorted in descending order. So we return the lexicographically smallest permutation which will be the reverse of the given arrangement.
  3. Else find the index j such that j>i and a[j] is the smallest number greater than a[i] in i+1 to size(array)-1.
  4. Swap the values between index i and index j.
  5. Reverse the array from index (i+1) till the end of the array.

Code for Finding the Next Permutation in C++

// Function next_permutation will find the next permutation in C++
	void next_permutation(vector<int>& v) {
    	int i=v.size()-2;
    	while(i>=0){
        	if(v[i]<v[i+1]){
            	break;
        	}
        	i--;
    	}
    	if(i<0){
        	reverse(v.begin(),v.end());
        	return;
    	}
    	int j=v.size()-1;
    	while(j>i){
        	if(v[j]>v[i]){
            	break;
        	}
        	j--;
    	}
    	int x=v[i];
    	v[i]=v[j];
    	v[j]=x;
    	reverse(v.begin()+i+1,v.end());
    	return;
	}

Time Complexity- O(N)

Where N is the number of elements present in the array.
For 1st backward iteration, Time Complexity O(N).
For 2nd backward iteration, Time Complexity O(N).
For swapping, Time Complexity O(1).
For reversing, Time complexity O(N).
To sum up overall Time Complexity is 3*O(N), which approximately becomes O(N).

Space Complexity- O(1)

No extra space is required. Thus its space complexity is O(1).

Dry Run for Next Greater Permutation in C++

Consider the input array [1, 3, 2].

  1. Traversing the array backward linearly and stop at the point where a[i] < a[i+1]. Initially i=sizeof array-2(i=1 in this case).

  1. Since i=1 and a[i]=3 and a[i+1]=2 and 3>2, decrease i by 1(i=0).

  1. Now i=0, a[i]=1 and a[i+1]=3 and 1< 3, which satisfies the condition, so break.
  2. Now, we have to find index j where j>i and a[j] is the smallest number greater than a[i]. We will traverse backward linearly again, Initially j=sizeof array -1 (j=2 in this case).

  1. j=2, and a[j]>a[i], so we have found the index value of j, so break.
  2. Swap the value at index i and index j.

  1. Reverse the array from index i+1.

This is the Next Greater Permutation of the given array.

Optimal Solution for Previous Smaller Permutation in C++

Intuition
Observe the following case:
Given Array Previous Smaller Permutation
1, 2, 3 Not Possible
2, 1, 3 1, 3, 2
1, 3, 2 1, 2, 3
3, 2, 1 3, 1, 2

We can observe that Previous Smaller Permutation is only possible if and only if the array is not ascendingly sorted.

We have to find the index i where a[i]>a[i+1]. Then find an index j such that i < j < size of array and a[j] is the largest number which is smaller than a[i]. And if the largest number is repeated more than once, take the index value j greater than i but as small as possible.

Approach to Find Previous Smaller Permutation

  1. Linearly traverse through the array from the backwards and find the index i such that a[i]>a[i+1].
  2. If index i is less than zero, then the given arrangement is the smallest arrangement possible (arranged in ascending order), so return the array as it is.
  3. Else find the index j such that j>i and a[j] is the largest value smaller than a[i]. If the largest number smaller than a[i] is repeated more than one then j should be as small as possible.
  4. Swap the values of index i and index j.

Code for finding the Previous Smaller Permutation in C++

vector<int> prev_permutation(vector<int>& a) {
    	int i=a.size()-2;
    	while(i>=0){
        	if(a[i]>a[i+1]){
            	break;
        	}
        	i--;
    	}
    	if(i<0){
        	return a;
    	}
    	int j=a.size()-1,mx=INT_MIN;
    	int y=a.size()-1;
    	while(j>i){
        	if(a[i]>a[j]){
            	if(mx<=a[j]){
                	y=j;
                	mx=a[j];
            	}
        	}
        	j--;
    	}
    	int x=a[i];
    	a[i]=a[y];
    	a[y]=x;
    	return a;
	}

Time Complexity- O(N)

Where N is the number of elements present in the array.
For 1st backward iteration, Time Complexity O(N).
For 2nd backward iteration, Time Complexity O(N).
For swapping, Time Complexity O(1).
To sum up overall Time Complexity is 2*O(N), which approximately becomes O(N).

Space Complexity- O(1)

No extra space is required. Thus its space complexity is O(1).

Dry Run for Previous Smaller Permutation in C++

Consider the input array [1,3, 2].

  1. Iterate the array backward and stop at the point where a[i]>a[i+1]. Initially i=sizeof array-2 (i=1 in this case).

  1. i=1, a[i]=3 and a[i]>a[i+1], so we have found the required i index, so break the loop.

  2. Now, we have to find index j such that j>i and a[j] has the largest value smaller than a[i]. In case of more than one index containing this value choose the index j as small as possible. We will traverse backward linearly again, Initially j=sizeof array -1 (j=2 in this case).Break the loop when j-1=i.

  1. j=2 and a[j] < a[i], here j-1=i so break the loop.

  2. Swap the values of index i and index j.

This the previous permutation of given array.

Leave a Reply

Your email address will not be published. Required fields are marked *