字典顺序,实际上就是一个递增的顺序。字典为 \(dic\) ,可以得到:\(dic[n] < dic [n+1]\)

\(dic[n]\) 记为 \(d_n\)\(dic[n+1]\) 记为 \(d_{n+1}\) ,相邻的两个元素,可能存在前N位相同的项(N可以为0),我们将前N项去掉。得到 \(S_n\)\(S_{n+1}\)

  1. 由于是递增顺序,显而易见: \(S_n[0] < S_{n+1}[0]\)

  2. 由于 \(S_n\) 的下一项是 \(S_{n+1}\) ,所以 \(S_n[1:]\) 的所有元素无法排列出比现有更大的组合。 \(S_n[1:]\) 为递减排列(即能排列出的最大值)。

    同样的道理, \(S_{n+1}\) 的上一项是 \(S_n\) ,所以 \(S_{n-1}[1:]\) 的所有元素无法排列出比现有更小的组合。 \(S_{n+1}[1:]\) 为递增排列。

    如果能排列出来,那与“ \(S_n\) 的下一项是 \(S_{n+1}\) ”相冲突

  3. 对于 \(S_n[0]\)\(S_{n+1}[0]\) ,除了已经知道的 \(S_n[0] < S_{n+1}[0]\) 。还有另外一个规律: \(S_{n+1}[0]\)\(S_n\) 所有元素中 \(S_n[0]\) 的下一项。(依然是因为 \(S_n\) 的下一项就是 \(S_{n+1}\)

所以,整体的思路是:

  1. 先从数组右端往左端查找,找到第一个不满足递减的位置。即,当前位置p,比右边小。右边是递减。
  2. 在右边的数组中,从左往右查找,找到最后一个大于nums[p]值的nums[t],交换两者的值,此时nums[p:]依然是一个递减的数组。
  3. 对nums[p:]进行逆序排列,nums[p:]变成递增。

代码:

func nextPermutation(nums []int) {
	var i = len(nums) - 1
	for i > 0 && nums[i] <= nums[i-1] {
		i--
	}
	p := i - 1
	if i != 0 {
		for i < len(nums) && nums[i] > nums[p] {
			i++
		}
		nums[p], nums[i-1] = nums[i-1], nums[p]
	}
	for i = 1; p+i < len(nums)-i; i++ {
		nums[p+i], nums[len(nums)-i] = nums[len(nums)-i], nums[p+i]
	}
}