# 31. Next Permutation

[https://leetcode.com/problems/next-permutation/](https://leetcode.com/problems/next-permutation/)

O(n), O(1)

[http://bangbingsyb.blogspot.com/2014/11/leetcode-next-permutation.html?m=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](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

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



假設是 1\~5

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

\[   ] 4 5321

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2F0O2eaQKVAQiN29lrMNgs%2Fimage.png?alt=media\&token=6e08fcbd-378c-41a3-9e5e-b0d5d672c03d)



```java
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

```java
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 

*/
```
