https://leetcode.com/problems/next-permutation/description/
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
For example:
1,2,3->1,3,2
3,2,1->1,2,3
1,1,5->1,5,1
給你一個數列，請基於字典編彙的權重規則，把下一個排列回傳給我。
(看example其實就很清楚)
[Solution] For example:
1,2,3->1,3,2
3,2,1->1,2,3
1,1,5->1,5,1
給你一個數列，請基於字典編彙的權重規則，把下一個排列回傳給我。
(看example其實就很清楚)
Let's solve this problem by asking some good questions:
1.What is the first and last permutation of sequence ?
Let's start from an observation :
For array [2,3,4], all permutations are 234, 243, 324, 342, 423, 432.
You will find that the first one "234" is in ascending order,
and last one "432" is in descending order .
It's a very important observation which lead to a conclusion :
1.the permutation of a sequence start from ascending order e.g. 234
2.the permutation of a sequence end at descending order e.g. 432
2.What happen when you want to get next permutation of a descending sequence such as 432?
You can not !! No matter how you adjust the order of 4,3,2, you cannot achieve the next permutation.
So we get a further conclusion :
If an sequence is already in descending order, the "Next Permutation" cannot be achieved by only adjust the order of numbers inside the sequence.
And let's start another observation :
If I add one more number '1' to the [2,3,4] and become [1,2,3,4], will I be able to solve the previous problem? Yes!
Let's see the 432 problem again.
1234, 1243, 1324, 1342, 1423, 1432.
Originally, I just adjust the order of 2 & 3 & 4 to get the next permutation. Then I fail to get the next permutation of 432. But we are not hopeless, there is a number '1' in front of 432. When you extend your view from 432 to 1432, you will find that 1432 is not in descending order. Which means you can get next permutation by adjust numbers in 1432.
So we get a further conclusion :
If a sequence is already in descending order(such as 432), but there is another number in front of them, and smaller than sequence head (such as 1 < 4 ). You will be able to get next permutation by introducing him into the sequence.
3.How do we adjust 1432 ??
A.The first postition
Let think who should be put on the first position. It is 1 or 2 or 3 or 4?
Of course not '1', it's trivial, if you choose '1' then nothing improved. So it must be 2 or 3 or 4.
It must be '2' because it is higher rank than '1', but smaller than '3','4'. If you choose '3' or '4', the index of the permutation increased too much. it's definitely not "the next permutation".
The one who is one more rank higher than the sequence head '1', which is '2' in this case, should be put on first position.
Please note that "one more rank" does not means their diff is one. 1->2 , 1->5 , 1->9 are one more rank higher, as long as there is no other rank between them.
B.The remaining position
After putting '2' on first position, there are three position left to be decided.
Since we picked '2' who is one more rank higher than '1' to be put in first position, the permutation index is increased because of this decision. So, for the rest of the numbers, we only need them to be the smallest index permutation they can be. That is the ascending order.
For the remaining numbers, they should be arranged as the smallest index permutation they can be, which means ascending order.
[Summary]
1.Scan from right to left, find the target who interrupt the descending order. (e.g. '1' in 71432)2.Reverse the descending part. (e.g 71432 --> 71234)
3.Swap target '1' with '2' who is one more rank higher than the target. (e.g. 71234 --> 72134)
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int target = nums.size()-2;
int end = nums.size()-1;
while(target >=0 && nums[target] >= nums[target+1]){//find the target
target--;
}
//reverse target+1 ~ End
for(int i=target+1, j=end; i<j; i++,j--){
swap(nums[i],nums[j]);
}
if(target >=0 ){
for(int i=1; target+i <= end ;i++){//find the first number bigger than target
if(nums[target] < nums[target+i] ){
swap(nums[target], nums[target+i]);
break;
}
}
}
return;
}
};
