Next Permutation find next lexicographically greater permutation
A permutation of an integer array is an arrangement of its items into linear order and the next permutation of an integer array is the next lexicographically greater permutation of its integer.
Given an array of integers, rearrange the numbers of the given array so that they form the lexicographically next larger permutation of numbers.
If such an arrangement is not possible, array must rearrange to the lowest possible order (sorted in ascending order).
Let's take an array arr = [1,2,3], all permutations of arr is
[1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1]
find next permutation of [1,3,2]
Output : [2, 1, 3]Find Next Permutation of [3,2,1]
Output : [1,2,3]
- 1 <= arr.length <= 100
- 0 <= arr[i] <= 100
- use only constant extra memory.
Brute Force: Finding all possible permutations.
Approach
- Find all possible permutations of array elements and store them.
- Search input array into from all possible permutations that we are stored in step 1.
- Print the next permutation.
- If search is the last permutation in this case print first permutation.
Time Complexity
Finding all possible permutations (step1) will take N!xN. Where N is the number of elements in the input array. after that we are searching input arrays from all possible permutations it will take N!. so Time complexity will be O(N!xN + N!) => O(N!xN)
Space Complexity
we are storing all possible permutations so space complexity will be O(N!)
Using C++ in-build function
In C++, the Standard Library (<algorithm>) provides a built-in method std::next_permutation to generate the next lexicographical permutation of a sequence.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> arr = {1, 3, 2};
next_permutation(arr.begin(), arr.end());
for (int i : arr) {
cout << i << " ";
}
cout << endl;
return 0;
}2 1 3
Next Permutation in linear time complexity
Approach
Let’s try to observe some patterns with example
arr [1,2,3,4]
all possible permutations :- [1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]
Observations :-- As we can observe there is a point from which the element on its left side is the same in it's next permutation. Let's call that point as Break point.
- Assigning (b) to break point in all possible permutation. [1, 2, 3(b), 4], [1, 2(b), 4, 3], [1, 3, 2(b), 4], [1, 3(b), 4, 2], [1, 4, 2(b), 3], [1(b), 4, 3, 2], [2, 1, 3(b), 4], [2, 1(b), 4, 3], [2, 3, 1(b), 4], [2, 3(b), 4, 1], [2, 4, 1(b), 3], [2(b), 4, 3, 1], [3, 1, 2(b), 4], [3, 1(b), 4, 2], [3, 2, 1(b), 4], [3, 2(b), 4, 1], [3, 4, 1(b), 2], [3(b), 4, 2, 1], [4, 1, 2(b), 3], [4, 1(b), 3, 2], [4, 2, 1(b), 3], [4, 2(b), 3, 1], [4, 3, 1(b), 2], [4, 3, 2, 1]
- If we observe any permutation from right to left we can see break point is first element of permutation from right side which right element is greater that it.
- At any permutation we can observe all element from break point to right side is sorted in descending order.
- We can observe that at any point of time for getting next permutation , break point is replaced by it's just greatest value from right side of elements.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void nextPermutation(int nums[],int n)
{
int i=0;
for(i=n-1; i>0; i--) {
if(nums[i]>nums[i-1]) {
int j=i,jmax=i;
while(j<n) {
if(nums[j]>nums[i-1] && nums[j]<nums[jmax]) {
jmax=j;
}
j++;
}
int temp=nums[i-1];
nums[i-1]=nums[jmax];
nums[jmax]=temp;
sort(nums+i,nums+n);
return;
}
}
if(i==0) {
sort(nums,nums+n);
}
}
int main()
{
int arr[] = {1, 3, 2};
int n = sizeof(arr) / sizeof(arr[0]);
nextPermutation(arr, n);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}2 1 3
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void swap(int nums[], int i, int j)
{
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
void nextPermutation(int nums[], int n)
{
int i = n - 1;
while (i > 0 && nums[i] <= nums[i - 1]) {
i--;
}
if (i <= 0) {
sort(nums,nums+n);
return;
}
int j=i, jmax=i;
while(j<n) {
if(nums[j]>nums[i-1] && nums[j]<nums[jmax]) {
jmax=j;
}
j++;
}
swap(nums, i-1, jmax);
sort(nums+i,nums+n);
}
int main()
{
int arr[] = {3, 2, 4, 1};
int n = sizeof(arr) / sizeof(arr[0]);
nextPermutation(arr, n);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}3 4 1 2
One more thing we observe here when we are swapping break point with just greatest element from right side. Our right side elements will be sorted in decreasing order so no need to apply sorting algorithm here if we just reverse the right side of elements from break point after swapping this will work as expected.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void swap(int nums[], int i, int j)
{
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
void reverse(int nums[], int start, int end) {
while (start < end) {
swap(nums, start, end);
start++;
end--;
}
}
void nextPermutation(int nums[], int n)
{
int i = n - 1;
while (i > 0 && nums[i] <= nums[i - 1]) {
i--;
}
if (i <= 0) {
reverse(nums,0,n-1);
return;
}
int j=i, jmax=i;
while(j<n) {
if(nums[j]>nums[i-1] && nums[j]<nums[jmax]) {
jmax=j;
}
j++;
}
swap(nums, i-1, jmax);
reverse(nums,i,n-1);
}
int main()
{
int arr[] = {3, 2, 4, 1};
int n = sizeof(arr) / sizeof(arr[0]);
nextPermutation(arr, n);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}3 4 1 2
Time Complexity
For finding break point is O(N) , finding next greatest number from break point O(N) , and reversing right side is O(N) so Time Complexity will be O(N+N+N) => O(3N) =>O(N)
Space Complexity
Since we are not using any extra storage so space complexity will be O(1).