algo-aha

第k个排列

• https://leetcode.com/problems/permutation-sequence/

string getPermutation(int n, int k) {
    // 首元素固定后剩余元素有(n-1)!种排列，
    // 第k（0-based）个排列的首元素是 k/(n-1)!
    vector<int> f(n, 1); // f[i]=i!
    for (int i = 1; i < n; i++) 
        f[i] = i * f[i-1];

    string s;
    for (int i = 1; i <= n; i++) 
        s += '0' + i;
    k--; // k变成0-based
    string ans;
    while (n) {
        int idx = k / f[n-1];
        ans += s[idx];
        k %= f[n-1];
        n--;
        s.erase(s.begin() + idx); // 剩余元素仍有序
    }
    return ans;
}

生成下一排列

• https://leetcode.com/problems/next-permutation
• https://leetcode.com/problems/next-greater-element-iii/

// 生成"下一排列"：
// 1. 从右往左找第一个波峰前的数，即找第一个nums[i]<nums[i+1]的位置i
// 2. 在i右边、从波峰往右是个递减序列，从右往左肯定能找到第一个>nums[i]的位置j
// 3. 交换nums[i]和nums[j]，交换后从波峰往右仍是个递减序列
// 4. 反转从波峰往右这个递减序列

void nextPermutation(vector<int>& nums) {
    const int N = nums.size();
    int i = N - 2;
    while (i >= 0 && nums[i] >= nums[i+1]) i--;
    if (i < 0) {
        reverse(nums.begin(), nums.end());
        return;
    }
    int j = N - 1;
    while (j > i && nums[j] <= nums[i]) j--;
    swap(nums[i], nums[j]);
    reverse(nums.begin() + i + 1, nums.end());
}