31. Next Permutation

[niuworld]

Question:

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, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its >corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2

3,2,1 → 1,2,3

1,1,5 → 1,5,1

Solution:

Next Permutation 存在于C++的标准库,使用的時候可以直接調用，

void nextPermutation(vector<int> &num) {  
      next_permutation( num.begin(), num.end() );  
   } 

但是面試回答的時候，卻不能這樣作答。關於next_permutation的解釋也蠻多的，我是從這篇文章理解到的。

From the wikipedia, one classic algorithm to generate next permutation is:

1. Find the largest index k, such that A[k]<A[k+1]. If not exist, this is the last permutation. (in this problem just sort the vector and return.)
2. Find the largest index l, such that A[l]>A[k].
3. Swap A[k] and A[l].
4. Reverse A[k+1] to the end.

然後再看問題中的例子：

1. 1,2,3 → 1,3,2: 當k ＝ 0，1 的時候，均有A[k+1]>A[k]，k的最大值為1-->找到最大索引（其數值大於A[k]）,找到 l ＝ 2 -->交換 A[k]和A[l]的位置-->將A[2]及以後的數列反轉。
2. 3,2,1 → 1,2,3 不存在 A[k]<A[k+1]，所以整個數組進行反轉。

code如下：

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int len = nums.size();
        int i = len-1;
        int k;
        if( len == 0) return;
       while  ( i > 0)
        { if ( nums[i-1] <  nums[i] )
          {k = i - 1 ;
           break;
          }
          --i;
       }
       if( i == 0){
         reverse(nums.begin(), nums.end());
         return;
       }
       int l;
       int j = k + 1;
       while( j <= len - 1)
       { if ( nums[j] > nums[k])
            l = j;
            j++;
       }
       swap(nums[k], nums[l]);
       reverse(nums.begin()+k+1, nums.end());
   }
};

Note:

1. 題目要求返回為void，要看清。
2. 循環中的要注意break的使用。
3. next_permutaion的意義在於使得數列按照字典中排序的方式排列。例如[3, 2, 7, 6, 3, 1], 其中「7，6，3，1」已經達到這四位排序的最大值。所以一定要動用2這個數字。需要選用剛好比2大的數字進行交換（在2後面的數字中挑選），交換后，2後面的數字需要進行升序排列。