C++でk番目の順列シーケンスを効率的に求める方法

問題の概要

集合 [1, 2, 3, ..., n] には、合計 n! 通りの異なる順列が存在します。すべての順列を辞書順に並べてラベルを付けると、n = 3 の場合は次のシーケンスが得られます。

["123", "132", "213", "231", "312", "321"]

このとき、n と k が与えられた場合、k 番目の順列シーケンスを返すのが本問題の目的です。制約として、n は 1 以上 9 以下、k は 1 以上 n! 以下の範囲にあります。

アルゴリズムの考え方

すべての順列を生成して k 番目を探す方法は非効率です。そこで、階乗の性質を利用したアプローチを用います。

先頭の桁にどの数字を置くかを決めるとき、残りの n-1 個の数字で作れる順列は (n-1)! 通りあります。つまり、k を (n-1)! で割ることで、k 番目の順列がどの「先頭数字のグループ」に属するかを特定できます。この処理を各桁に対して繰り返すことで、全体を n ステップで解決できます。

具体的な手順

• ans を空文字列として初期化し、サイズ n の候補配列 candidates を用意する
• i を 0 から n-1 までループし、candidates[i] := (i + 1) + '0' とする（数字文字の生成）
• サイズ n+1 の階乗配列 fact を作成し、fact[0] := 1 と初期化する
• i を 1 から n までループし、fact[i] := fact[i-1] × i とする
• k から 1 を引く（0 始まりのインデックスに変換）
• i を n-1 から 0 まで逆順にループする：
  • idx := k ÷ fact[i]（その桁に置く数字のインデックス）
  • ans := ans + candidates[idx]
  • 使用した数字を candidates から削除（左詰めで詰める）
  • k := k mod fact[i]（残りの順列内での位置を更新）
• ans を返す

C++での実装例

以下に、上記のアルゴリズムを実装したコードを示します。

#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);
}

実行結果

入力として n = 4、k = 9 を与えた場合の実行例を示します。

入力

4
9

出力

2314

計算量について

このアルゴリズムの時間計算量は O(n²) です。各桁の決定に O(n)、候補配列からの要素削除に O(n) かかるためです。ただし n は最大 9 と小さいため、実用上は十分高速に動作します。全順列を生成する O(n! × n) の素朴な手法と比べると、劇的な効率化が実現できています。