字典顺序

字典顺序，实际上就是一个递增的顺序。字典为 \(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]
	}
}