Next permutation

找出下一個排列，看似簡單，但是是一個數學題

當一個數字 724321 ，下一個排列要怎麼看?

我們首先會看後面的 4321，因為這邊已經是最大了，所以動也沒有用

於是看到 2，然後會想說 2 的下一個不就是 3 嗎? 可以跟 4321 裡面的 3 換，

換完變成 734221，這個並不是 724321 的下一個，因為結尾太大，

要將結尾反過來，便是答案 731224，可以整理成以下思路:

1. 找出由右往左的第一個遞減的數 (i)
2. 將這個數與 (i+1, len-1) 的第一個比自己大的數交換

3. 再將 (i+1, len-1) 反轉

4. 我們可以想一下，因為剛剛在 1 時，就已經知道這邊都是由右向左遞增的，所以無須排序，反轉即可

public int[] nextPermutation(int[] nums) {
    if (nums.length < 2) {
        return nums;
    }

    int len = nums.length;
    int i = len-1;
    // find the first descending point
    while (i-1>=0 && nums[i] <= nums[i-1]) {
        i--;
    }

    if (i == 0) {
        Arrays.sort(nums);
        return nums;
    }
    i--; // position i to the first descending elemnt

    int j = len-1;
    while (j>i && nums[j] <= nums[i]) {
        j--;
    }

    swap(nums, i, j);
    reverse(nums, i+1, len-1);
    return nums;

}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

private void reverse(int[] nums, int start, int end) {
    for (int i=start, j=end; i<j; i++, j--) {
        swap(nums, i, j);
    }
}

同場加映: previous permutation

道理是一樣的，不過改成要先找出由右往左的第一個上升點，找到後與由右往左第一個比自己小的數交換，交換後右邊部分做降序排列，因為剛剛在從右往左掃描時已經確定是由右往左降序，所以反轉後變成由右往左的升序，也就是是交換後的最大，也就是題目想要找的 previous permutation。