字典顺序,实际上就是一个递增的顺序。字典为 \(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}\) 。
-
由于是递增顺序,显而易见: \(S_n[0] < S_{n+1}[0]\) 。
-
由于 \(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}\) ”相冲突
-
对于 \(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}\) )
所以,整体的思路是:
- 先从数组右端往左端查找,找到第一个不满足递减的位置。即,当前位置p,比右边小。右边是递减。
- 在右边的数组中,从左往右查找,找到最后一个大于nums[p]值的nums[t],交换两者的值,此时nums[p:]依然是一个递减的数组。
- 对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]
}
}