下一个排列问题next_permutation
文章目录
- 下一个排列问题
- 一、问题引入
- 二、算法分析
- 三、总述
- 四、代码实现
- 五、问题变种
下一个排列问题
一、问题引入
全排列问题很常见，比如一个序列：1 2 3，它的全排列有6种：
1 2 3 、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1
但是如何根据一个排列求下一个排列？所谓下一个排列，就是比当前排列大，且字典序最小的排列。
比如2 3 1的下一个排列是3 1 2，因为比2 3 1大的排列中3 1 2是字典序最小的。
二、算法分析
以排列2 1 6 5 4 3为例，我们肉眼可见地清楚下一个排列应该是2 3 1 4 5 6，因为：
以2 1开头的排列已经达到了最大字典序。为什么是最大字典序？因为：
6 5 4 3是一个逆序序列。
此时再对这个逆序序列做排列，肯定是得不到更大的排列了。因此我们能做的就是修改这个逆序序列前面的部分，让前面部分的某一个数字变成一个更大的数字，此时才能获取下一个更大的排列。
那又如何决定修改前面部分的哪一个数字呢？很明显，是逆序序列的6 5 4 3前一个数字1。为什么？
因为1是前面部分数字的最低位，修改它给整个排列带来的增长肯定是最小的！
那么下一个问题，如何修改它？修改成多少呢？
既然我们已经决定修改逆序序列的前一个数字，那么该数字之前部分的就不需要修改了。而逆序序列已经达到最大排列，因此我们可以将逆序序列中取一个数和该数字交换。取哪一个数呢？
很明显，取3，因为3是这个逆序序列中比2大的最小的数字：
- 一方面，它大于
2，可以保证交换后，序列会变大。毕竟找一个小于等于2的数字交换，肯定会使下一个排列更小或者不变！ - 另一方面，交换后排列增大的幅度是最小的！因为它是逆序序列中比
2大的最小的数了。
当交换完毕后，逆序序列依然是一个逆序序列：
假设逆序序列前的数为x，逆序序列中比x大的最小数为y。
那么必然满足y右边的数比x小，y左边的数比x大。
所以x、y交换后，逆序序列依然保证是逆序的，将该逆序序列进行reverse，就可以让它恢复成最小字典序了(即递增)。
将逆序序列reverse的意义在于：
逆序序列前的那个数增大了，那么让这个逆序序列恢复成最小字典序，可以保证排列会增大，而且增大的幅度降至最小。
依然以2 1 6 5 4 3为例，找到3后交换，得到2 3 6 5 4 1，该序列比原先的排列要大，但是大太多了，因为6 5 4 1是个逆序序列，因此再将逆序序列reverse，得到2 3 1 4 5 6，这样，就获得了原排列的下一个排列。
三、总述
综上所述，算法的核心步骤如下：
i从后向前遍历，如果发现arr[i]>arr[i-1]则停止，此时arr[i]~arr[n-1]是一个递减的逆序序列。如果没有发现，则说明当前排列整体是一个逆序序列，它不存在一个更大的排列，2、3步骤不必进行。- 从后向前遍历
arr[i]~arr[n-1]，找到第一个比arr[i]大的arr[j]，将它们交换。 - 将
arr[i]~arr[n-1]翻转
四、代码实现
class Solution {
public:
void reverse(vector<int>& nums, int left, int right)
{
while (left < right)
{
swap(nums[left], nums[right]);
++left;
--right;
}
}
void nextPermutation(vector<int>& nums)
{
int n = nums.size();
for (int i = n - 1; i > 0; --i)
{
if (nums[i] <= nums[i - 1])
{
continue;
}
for (int j = n - 1; j >= i; --j)
{
if (nums[j] > nums[i - 1])
{
swap(nums[j], nums[i - 1]);
reverse(nums, i, n - 1);
return;
}
}
}
reverse(nums, 0, n - 1); // 走到这里说明当前排列是最大排列，将其恢复成最小排列
}
};
五、问题变种
下一个排列III