Next Permuatation: Leetcode
Given a vector of numbers. Find the next permutation.
This is a frequently asked interview question. Most people who have read the solution once would find this quite straight forward to answer when asked in an interview coding round or face to face one.
But those who are interested in figuring out the solution by yourself. Read on!
TLDR; This is an explanation of how to find the solution to next permuation from examples.
Let’s take an example 12568. It’s always good to take relatively large sequence. Since taking a small example like 123 won’t get you far since there are only a few permuations which go in the order 132, 213, 231,312 and 321.
Number of permutations for a n numbers is n! so take one that is large enough for you to derive observations.
Also notice that in all the examples you take the smallest number/ sorted list of numbers such that there is no permutation smaller than your initial one, because this helps you get to the next one much easier and without making any huge mistakes as it easier to navigate through ascending order and you are more likely to notice if you missed a permutation.
12568 next permutation is quite straight forward 12586 but whats after?
12856 going by how you swapped 6and 8 before. But you notice immediately that the next permutation should be 12658. Let’s go on by figuring out what the next one is like before without looking at patterns. So after 12658 we have
12865
12856
12865
15268
Ok! now we see huge shuffle in number. We swapped 5in 2’s place and rest of the number completely moved around from their initial position and numbers left of 5’s new spot seem to be untouched. No other significant pattern can be found without making huge speculations (Some of you might have already concluded that after swaping with 2 you sort all the numbers to the right, but it is too early to make this becuase multiple others are also valid. Like swap the righ most element, because we have been moving only our right most element so far). So let’s go on writing a few more.
15286
15628
15682
15862 here for the first time we swapped a number other than the first one. We can no notice that in 15682. 8>6 (156<8>2) but till 2 it has been ascending. It is reasonable to assume that we look for ascending from right to left. Even in the older examples you will notice the same but we were not able to conclude since it was always just a single element. Let’s go on
16285 Now 6 swapped into 5’s place and the rest all changes position. We again notice that in 15862 there is an ascending subarray 158>6>2 and it is suddenly violated at 5. Therefore the new position of one of the number in 8>6>2 is the position which 5 is at. We see this even in 128>6>5 where 5 took the place of 2. But which element do we replace it with?
We can conclude that the smallest element in the right of this position which exceeds the current is the one. 5 > 2 in 128>6>5 and it is the smallest. 6>5 in 158>6>2.
Therefore the solution is quite simple now. Find ascending subarray from left to right and swap the smallest element in subarray which exceeds the element adjacent to the subarray.
class Solution {
public:
void nextPermutation(vector<int>& nums) {
if(nums.size() == 1) return;
unsigned int swap_index = -1;
for(int i = nums.size()-1; i >= 1; i--) {
if(nums[i-1] < nums[i]) {
swap_index = i-1;
break;
}
}
if(swap_index == -1) {
sort(nums.begin(), nums.end());
return;
}
for(int i = nums.size()-1; i > swap_index; i--) {
if(nums[i] > nums[swap_index]) {
swap(nums[i], nums[swap_index]);
auto start = nums.begin()+swap_index+1;
sort(start, nums.end());
break;
}
}
You can find my complete notes here NEXT_PERMUATION_NOTES
