prev_permutation 和 next_permutation

prev_permutation和next_permutation都可以用在数组或者字符串上
prev_permutation返回前一个排列
next_permutation返回后一个排列
lc31

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        next_permutation(nums.begin(), nums.end());
    }
};
next_permutation(a, a + n);

acwing4307

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

string a, b;
bool st[20];
int n;

int main()
{
    cin >> a >> b;
    if(a.size() < b.size()) 
    {
        sort(a.begin(), a.end());
        reverse(a.begin(), a.end());
        cout << a;
        return 0;
    }
    n = a.size();
    string res;
    for(int i = 0; i < n; i++)
    {
        int p = -1;
        for(int j = 0; j < n; j++)
            if(a[j] == b[i] && !st[j])
            {
                st[j] = true;
                p = j;
                res += a[j];
                break;
            }
        if(p == -1) // 没有相等的，找小于
        {
            int pos = -1;
            for(int j = 0; j < n; j++)
                if(a[j] < b[i] && !st[j])
                {
                    if(a[j] - '0' > p)
                        p = a[j] - '0', pos = j;
                }
            if(p == -1) // 没有小于的
            {
                string r;
                for(int j = 0; j < n; j++)
                    if(!st[j]) 
                    {
                        r += a[j];
                        st[j] = true;
                    }
                sort(r.begin(), r.end());
                res += r;
                while(res > b)
                {
                    prev_permutation(res.begin(), res.end());
                }
                cout << res;
                return 0;
            }
            else // 有小于的
            {
                st[pos] = true;
                res.push_back(char(p + '0'));
                string r;
                for(int j = 0; j < n; j++)
                    if(!st[j])
                    {
                        r += a[j];
                        st[j] = true;
                    }
                sort(r.begin(), r.end());
                reverse(r.begin(), r.end());
                res += r;
                cout << res;
                return 0;
            }
        }
    }
    cout << res;
    return 0;
}

acwing842

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int w[10];

int main()
{
    int n;
    cin >> n;
    int sum = 1;
    for(int i = 1; i <= n; i++) sum *= i;
    for(int i = 1; i <= n; i++) w[i - 1] = i;
    for(int i = 0; i < sum; i++)
    {
        for(int i = 0; i < n; i++)
            cout << w[i] << ' ';
        cout << endl;
        next_permutation(w, w + n);
    }
    return 0;
}