Table of Contents
写这篇文章主要是因为二刷力扣时发现几道题目涉及到的知识相互关联，也就是说看完这篇文章，力扣的那几道题也就可以写出来了。
字典序
字典序是字典中索引的排序方法。一位一位的比较字母，以此排序。比如 add 和 advanced，前两个相同，无法判别，则根据第三位字母 d 在 v 之前。所以 add 在 advanced 之前。同理 abc 在 acb 之前。
现在有一串数字：[1,4,2,3,7,6,5]。需要得到字典序的下一个排列。[1,4,2,5,3,6,7]。
下一个排列需要符合两个条件（全升序为最小，全降序为最大）：
- 比当前排列大。
- 在之后的排列中最小。
如果单纯的找一个比 1 大的数互换，可以满足条件 1， 但不满足条件 2。要想 1 和 2 都满足，就需要按照字典序排列。
我们需要找到变动最小的点。这个点需要从后往前找，然后把这个点与点后比点大的数字中的最小者互换，最后点后的数字升序排序即可。
/* 图示
x
x x
x x x
x x x x
x x x x x
x x x x x x
x x x x x x x
-------------
从后方找到一个高峰（7），左侧的 3 即为需要交换的数字。然后从 3 后面倒序找第一个比 3 大的数字，得到 5。交换 3 和 5，然后将 5 后面三个数字倒转——山峰右侧为降序，倒转为升序。
*/
func nextPermutation(nums []int) {
length := len(nums)
left := -1
right := 0
for i := length - 1; i > 0; i-- {
// 峰值
if nums[i] > nums[i - 1] {
// 峰值左侧 A
left = i - 1
// A 右侧查找 B，使得 B > A
for j := length - 1; j > left; j-- {
if nums[j] > nums[left] {
right = j
break
}
}
nums[left], nums[right] = nums[right], nums[left]
break
}
}
for i, j := left + 1, length - 1; i < j; i, j = i + 1, j - 1 {
nums[i], nums[j] = nums[j], nums[i]
}
}
写完这个字典序的下一个排列，上面的四道力扣题就都可以解决了。但这篇文章还可以继续写点东西。
全排列
现在有几个数字：[1,2,3,4,5,6,7]，需要得到这个几个数字的全排列（返回顺序不重要）。
第一个排列可以认为就是 [1,2,3,4,5,6,7]。那么第二个呢？比把 1 和 2 互换得到 [2,1,3,4,5,6,7]。只要不重复，可以尽可能地尝试，直到 7! 个结果。
为什么是 7! 个结果？因为这是排列组合。第一位 7 种可能，第二位是剩下的 6 种可能……也就是说，以 1 开头有 6! 个结果，所以我们可以先得到 1 开头的 6! 个结果，然后在开始以 2 开头。以此类推，第 1、2 位固定的情况下，剩下的五位数有 5! 个结果。
这很容易想到递归。是的，递归可以。不过字典序也可以。并且字典序在解决有重复数字的全排列的时候不需要刻意去重，直接根据上一个排列得到下一个排列就可以了。
所以，直接复用上面的代码改改就行了。
康托展开和逆康托展开
现在，有 1~n 的 n 个递增数字，需要得到第 k 个排列。
能不能直接字典序解决呢？当然可以，排到第 k 个返回就是了。但这样会得到很多无用的排列，我们希望直接定位到第 k 个排列。
比如 n 为 7，k 为 46。我们知道以第一个数（1）开头有 6! 个结果。6! > 46，所以第一位是 1。那么第二位数呢？46 % 5！ 即可。
所以，第 m 位数即为剩下的结果数对 m 之后的位数的阶乘求余所得索引对应的数字。这里索引使用的数组是排除已用数字的数组。
func getPermutation(n int, k int) string {
nums := make([]int, n)
res := make([]string, n)
for i := 0; i < n; i++ {
nums[i] = i + 1
}
// 序列从 0 开始计数，k 要减去 1
k -= 1
for i := 0; i < n; i++ {
f := fac(n - 1 - i)
res[i] = strconv.Itoa(nums[k / f])
nums = append(nums[ : k / f], nums[k / f + 1 : ]...)
k %= f
}
return strings.Join(res, "")
}
func fac(n int) int {
res := 1
for i := 2; i <= n; i++ {
res *= i
}
return res
}
这就是“逆康托展开”。为什么先讲逆的？因为力扣题目需要这个，并且前面的字典序和全排列也是根据已有条件得到相应排列。
下面开始康托展开。
比如现在有一个排列：”1247563″，需要知道这是第几个排列。
这是上面操作的逆操作。
1 ~ 7 有 7! 种结果。根据首位不同，可以分为 7 组。很显然， “1247563” 位于第一组，因为第一位是 1。因此，其在 0 * 6! 个排列后面。再来，根据第二位得知其在第一组的第一分组里面，因为 1 已经被第一位占用了，剩下的数字之中，2 是最小的，所以为第一分组。因此其在 0 * 6! + 0 * 5! 后面。以此类推，可以得到结论：
X = an * (n – 1)! + an-1 * (n – 2)! + …… + a1 * 0!
其中 ai 的解释为：从原数字右往左第 i 个数，截至（左往右）i 位置，原数字中未使用的数中比 i 位置数字小的数字的个数。
这个公式和解释和上面一直从右往左的分析表述有点不同，因为康托展开就是这个公式。但意思是一样的。
还有一点，最后的 K 需要加一。因为 K 是指当前排列之前的排列数。
总结
基本上使用字典序就可以解决问题了，康托展开和逆康托展开算是补充。力扣“排列序列”这道题的官方解法也是逆康托展开，只是没有写明算法名称。