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の候補と呼ばれる配列を定義
• 0からn–1の範囲のiの場合
  • 候補者[i]：=（（i + 1）+文字「0」）
• サイズn+1のfactという1つの配列を作成し、fact [0]：=1を設定します
• 1からnの範囲のiの場合
  • fact [i]：=fact [i – 1] * i
• kを1減らします
• for i：=n –1から0まで
  • idx：=k / fact [i]
  • ans：=ans+候補者[idx]
  • for j：=idx、j +1<候補のサイズ
    • 候補者[j]：=候補者[j + 1]
  • k：=k mod fact [i]
• 回答を返す

理解を深めるために、次の実装を見てみましょう-

例

#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