Previous Permutation and Next Permutation in C++

Last Updated on April 17, 2023 by Prepbytes

Permutations are popular topics in mathematics and computer science. In computer science, permutations are used to solve a wide range of problems, such as generating all possible combinations of a set of elements, sorting algorithms, and generating test cases for software. In this article, we will learn the ways to find the next and previous, and next permutation in C++ of the given arrangement approaches and code implementation of the previous and next permutation in C++.

Previous and Next Permutation in C++

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 of Previous and Next Permutation in C++: 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 of Previous and Next Permutation in C++: 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 for next permutation in C++

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 the Next Permutation in C++

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).

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

3. Now i=0, a[i]=1 and a[i+1]=3 and 1< 3, which satisfies the condition, so break.
4. 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).

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

7. 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).

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

3. 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.

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

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

This the previous permutation of given array.

Conclusion
Now we can conclude the previous and next permutation in C++ with different approaches, Hope all approaches are clear and efficient to find the previous and next permutation in C++ The algorithms discussed in this article are efficient and widely used in practice. By using these algorithms, you can solve a wide range of problems that involve permutations in C++.

Frequently Asked Questions

Q1. What is the next permutation in C++?
Ans. The next permutation in C++ is a function from the C++ standard library that rearranges the elements of a container such that they form the lexicographically next permutation of the original container.

Q2. How is the next permutation implemented in C++?
Ans. The next permutation in C++ can be implemented in C++ using the std::next_permutation() function from the algorithm header.

Q3. Can these algorithms be used to generate permutations of non-integer types?
Ans. Yes, these algorithms can be used to generate permutations of any type that supports the less-than operator (<) and the swap function. For example, you can use these algorithms to generate permutations of strings, characters, or custom data types.

Q4. What happens if the sequence is already the largest or smallest permutation?
Ans. If the sequence is already the largest permutation, then the next_permutation algorithm will generate the smallest permutation. If the sequence is already the smallest permutation, then the prev_permutation algorithm will generate the largest permutation.