31. Next Permutation

https://leetcode.com/problems/next-permutation/

O(n), O(1)

http://bangbingsyb.blogspot.com/2014/11/leetcode-next-permutation.html?m=1

1. 從右到左找到第一個非升序的 index (pivot), (若找不到代表已經是最大排序, 要直接 reverse)

2. 找到後再從右到左, 找到比 nums[pivot] 大的元素

3. 做 swap

4. pivot 後的做 reverse

https://www.cnblogs.com/grandyang/p/4428207.html

[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

如果给定数组是 "降序"，则说明是全排列的最后一种情况，则下一个排列就是最初始情况

題目要的是 lexicographically next greater permutation of numbers

邏輯的思考, 我不可能改第一位, 如果想要大一點點, 會想從最低位開始, 但改了最低位, 其他位必定也要調整

假設是 1~5

[ ] 4321 => 這狀況下, 後面都已經是最大了, 如果想要更大就要去動到前面的部分了

[ ] 4 5321

class Solution {
    public void nextPermutation(int[] nums) {
        int pivot = findNonDescendingIndex(nums) - 1;
        if (pivot != -1) {
            int swapIndex = findGreaterThanPivot(nums, pivot);
            swap(nums, pivot, swapIndex);
        }
        reverse(nums, pivot+1);
    }
    
    private int findNonDescendingIndex(int[] nums) {
        for (int i = nums.length - 1 ; i > 0 ; i--) {
            if (nums[i] > nums[i-1]) {
                return i;
            }
        }
        return 0;
    }
    private int findGreaterThanPivot(int[] nums, int p) {
        for (int i = nums.length - 1; i >= p ; i --) {
            if (nums[i] > nums[p]) {
                return i;
            }
        }
        return -1;
    }
    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 s) {
        int e = nums.length - 1;
        while(s < e) {
            swap(nums, s++, e--);
        }
    }
}

new version

class Solution {
    public void nextPermutation(int[] nums) {
        int pivot = findPivot(nums);
        if (pivot == 0) {
            reverse(0, nums);
        } else {
            pivot = pivot-1;
            int swapTarget = findSwapTarget(nums, pivot);
            
            swap(nums, pivot, swapTarget);
            reverse(pivot+1, nums);
        }
    }
    private int findSwapTarget(int[] nums, int pivot) {
        for (int i = nums.length-1; i > pivot; i--) {
            if (nums[i] > nums[pivot]) {
                return i;
            }
        }
        return -1;
    }
    // 34321
    private int findPivot(int[] nums) {
        
        for (int i = nums.length - 1; i >= 1; i--) {
            if (nums[i] > nums[i-1]) {
                return i;
            }
        }
        
        return 0;
    }
    
    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
    
    private void reverse(int start, int[] nums) {
                    System.out.println(start);

        int left = start;
        int right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}

/*

4 521
swap
5 421 => 然後後面當然要最小的狀況, 所以做 reverse

=>
5 124


ex: 

[3]  8642  => 後面這部分不能在改動了, 因為無法更大, 由低位到高位是升序

所以就會打前面的主意

3 跟 後面比他大的交換（剛好大一點的, 也就是從低位 2, 4, ...

so 3 and 4 swap,

4  8632 => 後面在 reverse

4 2368

少動高位

1. find ascding order from last
2. if index numk not , swap this numk with the first number larger than numk (between numk+1 to end)
3. swap
4. reverse rest number (between numk+1 to end), because we want smallest one in the rest part
ex: 
[3]  8642
 4   8632
 4   2368 

*/