第k个排列

问题描述

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。

说明：
给定 n 的范围是 [1, 9]。
给定 k 的范围是[1,  n!]。

示例 1:
输入: n = 3, k = 3
输出: "213"

示例 2:
输入: n = 4, k = 9
输出: "2314"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-sequence

思路

逆康托展开
详细见 https://blog.csdn.net/wbin233/article/details/72998375，我感觉讲的挺详细的。

题解

class Solution {
public:
    vector<char> ch={'1','2','3','4','5','6','7','8','9'};
    vector<int> FAC={1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
    string getPermutation(int n, int k) {
        string ret;
        k=k-1;//排名第k名，所以有k-1个排序比它小的
        for(k;n--;k%=FAC[n]){
            const int i=k/FAC[n];
            ret+=ch[i];
            ch.erase(ch.begin()+i);去除下标为i的元素。
        }
        return ret;
    }
};