1. 题目描述
给定一个长度为n的数组，实现一个算法，计算这个数组的下一个排列。
2. 解法
在解决这个问题之前，我们需要了解一些关于排列的知识。下面给出了一些定义，涉及到下一个排列、字典序和一个我自己定义的关键子序列。
3. 下一个排列
- 下一个排列
- 设一个排列 $P = (p_1, p_2, \ldots, p_n)$，它是由集合 ${1, 2, \ldots, n}$ 的元素按某种顺序排列而成的一个序列。下一个排列 $P’ = (p’_1, p’_2, \ldots, p’_n)$ 是满足以下条件的最小排列：
- $P’$ 是由 ${p_1, p_2, \ldots, p_n}$ 的所有元素组成的一个排列。
- $P’$ 在字典序中比 $P$ 大。
- 在所有满足条件1和条件2的排列中，$P’$ 是字典序最小的。
4. 字典序
- 字典序
- 对于两个排列 $P = (p_1, p_2, \ldots, p_n)$ 和 $Q = (q_1, q_2, \ldots, q_n)$，如果存在某个位置 $k$ 使得 $p_i = q_i$ 对所有 $i < k$ 成立，并且 $p_k < q_k$，则称 $P$ 在字典序上小于 $Q$。
由上述定义可知，一个逆序排列是字典序最大的排列。因此，如果一个排列是逆序排列，那么它就没有下一个排列。
5. 关键子序列（Pivot Subsequence）
- 关键子序列（Pivot Subsequence）
- 设排列 $P = (p_1, p_2, \ldots, p_n)$。关键子序列是从排列 $P$ 的末尾开始，向左找到的第一个不满足升序关系的元素以及之后的所有元素所构成的子序列。关键子序列 $S$ 的定义如下：
关键子序列由如下性质：
-
调整性质：只需要将关键子序列进行调整得到关键子序列的下一个排列，就可以得到整个排列的下一个排列。
-
唯一性质：在一个排列中，关键子序列是唯一的。
-
单调递减性质：关键子序列中除了第一个元素之外，其余元素都是单调递减的。即 $(p_{k+1}, p_{k+2}, \ldots, p_n)$ 是单调递减的。
下面是对关键子序列性质的证明
5.1. 调整性质
设 $P = (p_1, p_2, \ldots, p_n)$ 是一个长度为 $n$ 的排列。假设排列 $P$ 的最后 $m$ 个元素 $(p_{n-m+1}, \ldots, p_n)$ 有下一个排列。设这个下一个排列为 $(q_{n-m+1}, \ldots, q_n)$，那么 $P$ 的下一个排列可以表示为：
\[P' = (p_1, p_2, \ldots, p_{n-m}, q_{n-m+1}, \ldots, q_n)\]其中，$(q_{n-m+1}, \ldots, q_n)$ 是 $(p_{n-m+1}, \ldots, p_n)$ 的下一个排列。
5.1.1. 正确性证明
要证明上述描述的正确性，我们需要证明以下两点：
-
$P’$ 比 $P$ 大
由于 $(q_{n-m+1}, \ldots, q_n)$ 是 $(p_{n-m+1}, \ldots, p_n)$ 的下一个排列，按照定义有：
\[(p_{n-m+1}, \ldots, p_n) < (q_{n-m+1}, \ldots, q_n)\]即在字典序上，$(p_{n-m+1}, \ldots, p_n)$ 比 $(q_{n-m+1}, \ldots, q_n)$ 小。而 $(p_1, p_2, \ldots, p_{n-m})$ 在 $P$ 和 $P’$ 中是相同的，因此整个排列 $P’$ 比 $P$ 大。
-
$P’$ 是所有比 $P$ 大的排列中字典序最小的
为了证明这一点，我们需要考虑所有可能的排列形式。假设存在另一个排列 $R$，使得 $R$ 比 $P$ 大且字典序小于 $P’$。我们分两种情况讨论：
-
如果 $R$ 的前 $n-m$ 个元素与 $P$ 的前 $n-m$ 个元素不同，即存在某个位置 $k$ $(1 \leq k \leq n-m)$，使得 $r_k \neq p_k$，那么 $R$ 比 $P$ 大的唯一可能情况是 $R$ 的前 $n-m$ 个元素中某个位置的值大于对应的 $P$ 的值。但是这种情况的 $R$ 必然会比 $P’$ 大，因为 $P’$ 保持了 $P$ 的前 $n-m$ 个元素不变，而 $R$ 改变了这些元素。
-
如果 $R$ 的前 $n-m$ 个元素与 $P$ 的前 $n-m$ 个元素相同，即 $R$ 的形式为：
而 $R$ 比 $P$ 大的唯一可能情况是 $(r_{n-m+1}, \ldots, r_n)$ 比 $(p_{n-m+1}, \ldots, p_n)$ 大。在这种情况下，$(r_{n-m+1}, \ldots, r_n)$ 必须在字典序上比 $(q_{n-m+1}, \ldots, q_n)$ 小，这与 $(q_{n-m+1}, \ldots, q_n)$ 是 $(p_{n-m+1}, \ldots, p_n)$ 的下一个排列的定义相矛盾。因此，不存在这样的 $R$ 使得它比 $P$ 大且字典序小于 $P’$。
-
由于关键子序列$S$就是从排列$P$的末尾开始，向左找到的第一个不满足升序关系的元素以及之后的所有元素所构成的子序列，因此，只需要将关键子序列进行调整得到关键子序列的下一个排列，就可以得到整个排列的下一个排列。
5.2. 唯一性&单调递减性质
这两个性质都可以通过关键子序列的定义直接得到。
6. 算法
根据关键子序列的性质，我们可以得到下一个排列的算法：
- 从右向左找到第一个不满足升序关系的元素，记为 $k$。
- 如果不存在这样的 $k$，说明整个排列是逆序排列，没有下一个排列。此时，将整个排列逆序即可。
- 否则，找到关键子序列 $S = (p_k, p_{k+1}, \ldots, p_n)$。
- 将关键子序列 $S$ 调整为下一个排列。
6.1. 调整关键子序列
调整关键子序列的方法如下：
-
找到第一个大于 $p_k$ 的元素： 从关键子序列的末尾开始向前遍历，找到第一个大于 $p_k$ 的元素 $p_l$。
-
交换 $p_k$ 和 $p_l$： 将 $p_k$ 和 $p_l$ 交换位置。
-
反转子序列 $(p_{k+1}, p_{k+2}, \ldots, p_n)$： 将子序列 $(p_{k+1}, p_{k+2}, \ldots, p_n)$ 反转，使其成为字典序最小的排列。
6.1.1. 证明
为了证明以上步骤找到的排列是整个排列的下一个排列，我们需要证明两点：
-
新排列比原排列大
假设关键子序列 $S = (p_k, p_{k+1}, \ldots, p_n)$。根据关键子序列的定义，$p_k < p_{k+1}$，且 $(p_{k+1}, \ldots, p_n)$ 是单调递减的。
- 找到第一个大于 $p_k$ 的元素 $p_l$。
- 交换 $p_k$ 和 $p_l$ 之后，新排列的前部分为 $(p_1, p_2, \ldots, p_{k-1}, p_l)$，后部分为 $(p_{k+1}, \ldots, p_{l-1}, p_k, p_{l+1}, \ldots, p_n)$。
- 由于 $p_k < p_l$，所以新排列比原排列大。
-
新排列是所有比原排列大的排列中字典序最小的
为了证明这一点，我们需要说明交换 $p_k$ 和 $p_l$ 后，再将后部分反转得到的排列是字典序最小的：
-
交换 $p_k$ 和 $p_l$： 交换后得到$p_l$之后的部分 $(p_{k+1}, \ldots, p_{l-1}, p_k, p_{l+1}, \ldots, p_n)$，由于 $p_l$ 是从右向左第一个大于 $p_k$ 的元素，交换后新排列比原排列大，并且在新的位置 $p_k$ 保持了相对顺序。也就是$(p_{k+1}, \ldots, p_{l-1}, p_k, p_{l+1}, \ldots, p_n)$是单调递减的。
-
反转子序列 $(p_{k+1}, p_{k+2}, \ldots, p_n)$： 反转后部分使其成为字典序最小的排列。反转的原因是原序列 $(p_{k+1}, \ldots, p_n)$ 是单调递减的，反转后变为单调递增，从而在字典序上最小。
-
因此，通过上述步骤找到的排列是整个排列的下一个排列。
7. 代码
注: leetcode中这个题的序列可能会有重复的数字，需要考虑这种情况
void nextPermutation(vector<int>& nums) {
int n = nums.size(), i = n - 2, j = n - 1;
while (i >= 0 && nums[i] >= nums[i + 1]) --i;
if (i >= 0) {
while (nums[j] <= nums[i]) --j;
swap(nums[i], nums[j]);
}
reverse(nums.begin() + i + 1, nums.end());
}