学过组合数学，都知道，排列可以通过不断的交换元素来实现。

比如序列 1 2 4 6 5 3
下一个更大的排列 为 1 2 5 3 4 6

要想获得一个更大的排列，那么要从右边找一个较大的数和左边一个较小的数进行交换

问题就变成了，如何去找这个较大的数和这个较小的数

考虑数列的单调性:

如果，从后往前看数列是单调递增的，无法通过交换该区间内的任何元素，使得排列变大

设要交换的下标为 i,
则 i 一定不在该单调递增的区间内
而且因为是要找下一个排列，
所以i 的位置要尽量靠右边，所以可以考虑从右往左枚举，找到第一个下降点。
以改点作为基准点

而又因为 i 是右边单调区间的第一个下降点
所以在区间[i+1,n] 之间，比能找到一个 比a[i] 要大的数

找到这个区间里，比a[i] 第一个大的数即可 设其下标为j
因为[i+1,n] 从 右向左为单调递增，所以从右往左枚举即可，第一个大的数就是右基准点

然后交换 i,j 即 swap(a[i],a[j]);

例题 1:
lc31:下一个排列

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = nums.size()-1;
        while(i>=1 && nums[i]<=nums[i-1]){
            i--;
        }
        if(i==0){
            sort(nums.begin(),nums.end());
            return;
        }
        i--;
        int j = nums.size()-1;
        while(j>i && nums[j]<=nums[i]){
            j--;
        }
        swap(nums[i],nums[j]);
        sort(nums.begin()+i+1,nums.end());
    }
};

例题2:P1088 火星人

#include<iostream>
#include<algorithm>

using namespace std;
const int MAXN = 1e4+5;
int arr[MAXN];
int n,k;

void nextPerm(){
    int i = n;
    for(;i>=2;i--){
        if(arr[i]>arr[i-1]){
            break;
        }
    }
    if(i==1){
        sort(arr+1,arr+n+1);
        return;
    }
    i--;
    int j = n;
    for(;j>=i;j--){
        if(arr[j]>arr[i]){
            break;
        }
    }
    swap(arr[i],arr[j]);
    sort(arr+i+1,arr+n+1);
}

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    for(int i=0;i<k;i++){
        nextPerm();
    }
    for(int i=1;i<=n;i++){
        cout<<arr[i]<<" ";
    }
    cout<<endl;
    return 0;
}