31. Next Permutation

This is more a math problem. The idea is to inspired by the case that the sequence is in reverse order. In that case we need to reverse the whole sequence to get the next permutation. By observing this, we can see that the next sequence will be to find the reverse order subsequence and reverse that sequence first. After reversing, we need to do one more extra step, i.e. swap the pivot who breaks the reverse order with the first number that is larger than the pivot in the new subsequence.

The algorithm is
(1) In reverse order, find the first number such that nums[i] < nums[i+1]. We say this number as pivot.
(2) Reverse the nums behind the pivot, i.e. nums.begin()+i+1 to nums.end();
(3) Find the first number that is larger than pivot.
(4) swap pivot with this number.

Example:
1,2,4,5,3
(1) Find pivot is 4.
(2) Reverse the numbers behind pivot, i.e. 1,2,4,3,5
(3) The first number that is larger than pivot is 5
(4) swap them, i.e. 1,2,5,3,4
Note, if the sequence is 3,2,1, we only need to reverse the array.

1:  class Solution {  
2:  public:  
3:    void nextPermutation(vector<int>& nums) {  
4:      if (nums.empty()) return;  
5:      int i = 0, j = 0;  
6:      for (i = nums.size() - 2; i >= 0 ; i--) {  
7:        if (nums[i] < nums[i+1]) break;  
8:      }  
9:      reverse(nums.begin()+i+1, nums.end());  
10:      if (i == -1) return;  
11:      for (j = i+1; j < nums.size(); j++) {  
12:        if (nums[j] > nums[i]) break;  
13:      }  
14:      swap(nums[i], nums[j]);  
15:    }  
16:  };