Problem Statement
A permutation of an array of integers is an arrangement of its members into a sequence or linear order.
- For example, for
arr = [1,2,3], the following are all the permutations ofarr:[1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].
The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such an arrangement is not possible, the array must be rearranged in the lowest possible order (i.e., sorted in ascending order).
For example, the next permutation of
arr = [1,2,3]is[1,3,2].Similarly, the next permutation of
arr = [2,3,1]is[3,1,2].While the next permutation of
arr = [3,2,1]is[1,2,3]Because[3,2,1]does not have a lexicographical larger rearrangement.
Given an array of integers nums, find the next permutation of nums.
The replacement must be in place and use only constant extra memory.
Algorithm
Pivot Point: If you observe the dictionary, you will notice a pattern: the right side of the word always increases from the end. The element after which the increasing trend stops is called the pivot point in this context.
What's Next: Now, replace the elements before the pivot point with the nearest greater number from the right half.
Sort: Next, reverse the right half, including the pivot point, to obtain the result. (Sort also works)
Why reverse the right part?
Because the pivot point is the maximum number, it implies that the right part is sorted in reverse order. One easy way to think about it is that the sorted descending array is the last possible permutation one can achieve. The same thing applies if we consider only the right part; it achieves the maximum possible permutation.
Explanation:
Choose any number and note down the next number in the sequence. In our human process, we find the index of the maximum element, replace the previous element with the next nearest greater element and then write down the remaining elements in ascending order. Expressing the elements in ascending order is essentially a form of sorting.
Edge case 1: The above logic holds true for the sorted array also
Edge case 2: If the elements are reverse-sorted, it implies there are no pivot elements. The last number in the dictionary is, therefore, the next number, which will be the reverse of this number or a sort of this array.
Solution Code:
Python -
pivot = -1
for i in range(len(nums)-1, 0,-1):
if nums[i-1]<nums[i]:
pivot = i
break
if pivot == -1:
nums.sort()
return
# print(pivot)
for i in range(len(nums)-1,pivot-1,-1):
if nums[pivot-1]<nums[i]:
# print(i)
nums[pivot-1],nums[i] = nums[i], nums[pivot-1]
break
nums[pivot:] = sorted(nums[pivot:])
Note: Sorting will consume extra time than reversing.
Java -
Note: Here we considered pivot point index is 1 less. This approach will also give the same result and also here we reversed instead of sorting.
class Solution {
public void nextPermutation(int[] nums) {
int pivot = -1;
// Find the pivot
for (int i = nums.length - 1; i > 0; i--) {
if (nums[i] > nums[i-1]) {
pivot = i - 1;
break;
}
}
if (pivot == -1) {
reverse(nums, 0, nums.length - 1);
return;
}
// Find the first element that is larger than pivot
int firstLarger = -1;
for (int i = nums.length - 1; i > pivot; i--) {
if (nums[i] > nums[pivot]) {
firstLarger = i;
break;
}
}
// Swap pivot and firstLarger
swap(nums, pivot, firstLarger);
// Reverse the subarray after pivot
reverse(nums, pivot + 1, nums.length - 1);
return;
}
private void reverse(int[] nums, int i, int j) {
while (i < j) {
swap(nums, i++, j--);
}
return;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i++] = nums[j];
nums[j--] = tmp;
return;
}
}