博客

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

1,2,3 → 1,3,2

3,2,1 → 1,2,3

1,1,5 → 1,5,1

看一下代码：

func nextPermutation(nums []int)  {
    if len(nums) == 0 || len(nums) == 1 {
        return
    }
    // 从右往左找到第一个nums[i]>[i-1]
    i := len(nums)-1
    for i > 0 && nums[i] <= nums[i-1] {
        i--
    }
    // 如果整个数组是降序，则不存在下一个更大的排列，翻转数组可得最小的排列
    if i == 0 {
        reverse(nums)
        return
    }
	
    // 如果存在下一个更大的排列，由于nums[i]>nums[i-1]&&nums[i:]为降序排列，所以nums[i:]从后往前寻找第一个比nums[i-1]大的数，进行交换
    for j := len(nums)-1; j >= i; j-- {
        if nums[i-1] < nums[j] {
            nums[i-1], nums[j] = nums[j], nums[i-1]
            // 交换后，翻转仍旧降序排列的nums[i]即可
            reverse(nums[i:])
            return
        }
    }
}

func reverse(nums []int) {
    i, j := 0, len(nums)-1
    for i < j {
        nums[i], nums[j] = nums[j], nums[i]
        i++
        j--
    }
    return
}

举个排列的例子:1 5 8 4 7 6 5 3 1  他的下一个排列是  1 5 8 7 4 6 5 3 1，因为1 5 8 6 7 4 5 3 1比前一个小且大于1 5 8 4 7 6 5 3 1。那个下一个排列的意思就是：比原数组排列大的所有组合中，最小的那个组合，其实这里我感觉题目没说清楚。

4 < 7，则i=4，i对应的这个位就是从右开始升序最大的那个数，然后在开始从右边进行遍历，找到第一个比a[i-1]大的数然后交换位置，交换后，a[i]后面就是(包括a[i])就是升序的，所以把其变为降序，最后组合的值越小。

代码地址：

https://www.cnblogs.com/nini-skyrim/p/12677352.html