C ++中的置换序列

假设集合像[1,2,3，...，n]，总共包含n个！独特的排列。通过按顺序列出并标记所有排列，我们得到n = 3的这些序列：[“ 123”，“ 132”，“ 213”，“ 231”，“ 312”，“ 321”]因此，如果n和k给出，然后返回第k个排列序列。n将在1到9（含）之间，而k将在1到n之间！（包括的）。例如，如果n = 3。

让我们看看步骤-

• ans：=空字符串，定义大小为n的候选数组

• 对于i，范围为0至n – 1

• 候选人[i]：=（（（i +1）+字符'0'）

• 创建一个称为大小为n + 1的事实的数组，设置fact [0]：= 1

• 对于我在1到n范围内

• fact [i]：= fact [i – 1] * i

• 将k减1

• 对于i：= n – 1降至0

• 候选人[j]：=候选人[j + 1]

• idx：= k /事实[i]

• 答案：=答案+候选人[idx]

• 对于j：= idx，j + 1 <候选大小

• k：= k mod事实[i]

• 返回ans

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   string getPermutation(int n, int k) {
      string ans = "";
      vector <char> candidates(n);
      for(lli i = 0; i < n; i++)
         candidates[i] = ((i + 1) + '0');
      vector <lli> fact(n + 1);
      fact[0] = 1;
      for(lli i = 1; i <= n; i++)
         fact[i] = fact[i - 1] * i;
      k--;
      for(lli i = n - 1; i >= 0; i--){
         lli idx = k / fact[i];
         ans += candidates[idx];
         for(lli j = idx; j + 1< candidates.size(); j++)
            candidates[j] = candidates[j + 1];
         k = k % fact[i];
      }
      return ans;
   }
};
main(){
   Solution ob;
   cout << ob.getPermutation(4, 9);
}

输入值

4
9

输出结果

2314