全排列中获取下一个排列的实现（c++ STL next_permutation）

维基百科中的步骤：

1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index l greater than k such that a[k] < a[l].
3. Swap the value of a[k] with that of a[l].
4. Reverse the sequence from a[k + 1] up to and including the final element a[n].

至于为什么这么做就可以得到下一个排列，可以看代码及注释。

实现代码：

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if(nums.size()==1) return;
        // find the largest index i which statisfies nums[i]<nums[i+1]
        // 从后往前找到交换点i，交换点i以后的数全部都是降序的
        // 因为i后面的数[i+1, n)已经无法变得更大，所以我们不得不让i位置变大一点来得到下一个序列
        int i=nums.size()-2;
        while(i>=0 && nums[i]>=nums[i+1]) {
            i--;
        }
        if(i<0) {
            // 如果找不到这么一个位置i，表示整个序列都是降序的，即已经是最后一个排列。
            // 重新得到第一个排列的方法是整个数组逆序。
            reverse(nums.begin(), nums.end());
            return;
        }
        // 可想而知，为了是变大程度尽量小，i前面的数不应该改动，我们从i后面的数里面挑出一个比i稍大的
        // 因为后面是降序，所以可以直接按位置查找
        // find the largest index j which statisfies nums[j]>nums[j]
        int j=nums.size()-1;
        while(nums[j] <= nums[i]) {
            j--;
        }
        // 我们将这个数nums[j]交换到nums[i]的位置
        swap(nums[i], nums[j]); 
        // 因为我们找到的nums[j]是比nums[i]刚刚稍小的数，所以交换完成后，后面的区间[i+1,n]仍然是降序的
        // 此时还没有结束。因为后面的区间[i+1,n]是降序的，我们知道降序是最大的排列（最后一个排列）而不是最小的排序
        // 我们将这个降序区间调整回为升序区间，此时才是下一个排列
        reverse(nums.begin()+i+1, nums.end());
    }
};

相关练习题：https://leetcode.cn/problems/next-permutation

参考资料：
https://leetcode.cn/problems/next-permutation/solution/xia-yi-ge-pai-lie-by-leetcode-solution/
https://leetcode.cn/problems/next-permutation/solution/xia-yi-ge-pai-lie-by-powcai/
https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

Donate