Next Permutation

Next Permutation

 

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



Naive Way: 审题：1.recursion 2. in-place
是在一个数组上 in-place 进行的，那么就只有 覆盖原来的(overlap) 和 交换两个数(swap) 。
通过探讨它的原理我发现可以这样找，

1.从后往前遍历，应该是递增（从后往前）的，找到第一个非递增。

2.那个点就是要升位一个的点 t，在刚才来的路上找到比该数大且最接近的数 s，用该数 s 替代它（升位）。

3.后面的部分需要是从前往后看递增的，而之前来的路上一切都是递减的，所以倒过来写就可以了，相当于两头交换。

4.但是还有一个数要处理的就是 t 这个数本身，可以在交换好后，从 s 所在位置往后遍历一遍插入对应的位置。

实际做的时候发现第4步是多余的，因为交换了 t 和 s 的位置后，并不会打乱原来递减的顺序。还有一点就是找 s 的位置一定要找相同差值下最后面的位置，比如两个3，就要取后面的3，因为要保持后半部分的递减性。

算法复杂度O(n), space O(1)。

public class Solution {
    public void nextPermutation(int[] num) {
        int t,s;
        int i = num.length-1;
        while(i > 0 && num[i-1] >= num[i]) i--;
        if(i > 0){
            t = i-1;
            // search for nearest value larger than num[t] in num[i~length]
            s = i;
            for(int j = i;j < num.length;j++)
                if(num[j] > num[t] && num[j]-num[t] <= num[s]-num[t])
                    s = j;
            // swap position t and s
            num[t] = num[s] + num[t];
            num[s] = num[t] - num[s];
            num[t] = num[t] - num[s];
        }
        swapHeadAndTail(num, i, num.length-1);
        return;
    }
    
    private void swapHeadAndTail(int[] num, int begin, int end){
        while(begin < end){
            num[begin] = num[end] + num[begin];
            num[end] = num[begin] - num[end];
            num[begin] = num[begin] - num[end];
            begin++;
            end--;
        }
        return;
    }
}


以下是我第一次写的，应该当时不会写，是抄的。

public class Solution {
    public void nextPermutation(int[] num) {
        int i = num.length-1;
        int j;
        while(i > 0){
            if(num[i] > num[i-1])
                break;
            i--;
        }
        if(i != 0){
            for(j = i;j < num.length;j++)
                if(num[j] <= num[i-1])
                    break;
            swap(num, i-1, j-1);
        }
           
        reverse(num, i, num.length-1);
    }
   
    private void reverse(int[] A, int begin, int end){
        for(int i = begin;i <= (end+begin)/2;i++)
            swap(A,i,end+begin-i);
    }
   
    private void swap(int[] A, int a, int b){
        int temp = A[a];
        A[a] = A[b];
        A[b] = temp;
    }
       
}