C++で文字列のn番目の辞書式順列を求める方法

概要

小文字のアルファベットのみで構成された長さmの文字列が与えられたとき、その文字列の順列を辞書順に並べた場合のn番目の順列を求めるのがこの問題の目的です。

入力例

str[] = "pqr", n = 3

出力例

Result = "qpr"

解説

「pqr」のすべての順列を辞書順に並べると、pqr、prq、qpr、qrp、rpq、rqp の6通りになります。3番目は「qpr」です。

入力例

str[] = "xyx", n = 2

出力例

Result = "xyx"

解説

重複した文字を含む場合、「xyx」の順列を辞書順に並べると、xxy、xyx、yxx の3通りになります。2番目は「xyx」です。

解法の考え方

この問題は、すべての順列を実際に生成しなくても、数学的な性質を利用することで効率的に解くことができます。基礎となる事実は次のとおりです。

• N個の相異なる文字から作れる順列の総数は N! 通りです。
• N個の文字のうち、文字C1がM1個、C2がM2個…CkがMk個含まれる場合、順列の総数は N!/(M1! × M2! × … × Mk!) で求められます。
• 先頭の1文字を固定した場合、残りの文字で作れる順列の総数も同じ式で計算できます。

アルゴリズムの手順

1. まず、各文字の出現回数を配列freq[]に記録します。
2. 文字列に存在する最小の文字（freq[i] > 0 となる最小のインデックスi）から順に、その文字を先頭に固定したときに作れる順列の総数を計算します。
3. 累積値がn以上になったら、その文字を出力の先頭文字として確定し、freq[i]を1減らして、残りの文字に対して同じ処理を続けます。
4. 累積値がn未満の場合は、頻度表の次の文字に進み、n以上になる文字が見つかるまで累積値を更新し続けます。

この手法の時間計算量はO(n)であり、文字列の長さに比例したオーダーで処理できる点が大きな特徴です。

サンプルコード

// n番目の順列を出力する
// C++プログラム
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int MAX_CHAR1 = 26;
const int MAX_FACT1 = 20;
ll fact1[MAX_FACT1];
// 階乗を計算するユーティリティ関数
void precomputeFactorials(){
    fact1[0] = 1;
    for (int i = 1; i < MAX_FACT1; i++)
        fact1[i] = fact1[i - 1] * i;
}
// n番目の順列を求める関数
void nPermute(char str1[], int n1){
    precomputeFactorials();
    // 与えられた文字列の長さ
    int len1 = strlen(str1);
    // すべての文字の
    // 出現頻度をカウント
    int freq1[MAX_CHAR1] = { 0 };
    for (int i = 0; i < len1; i++)
        freq1[str1[i] - 'a']++;
    // 出力文字列用のバッファout1
    char out1[MAX_CHAR1];
    // sum1がn1と等しくなるまで繰り返す
    int sum1 = 0;
    int k1 = 0;
    // このループ内でn1とsum1を更新する
    while (sum1 != n1) {
        sum1 = 0;
        // freq1[]に存在する文字を確認
        for (int i = 0; i < MAX_CHAR1; i++) {
            if (freq1[i] == 0)
                continue;
            // 文字を取り除く
            freq1[i]--;
            // 特定の文字を固定した後の
            // sum1を計算
            int xsum1 = fact1[len1 - 1 - k1];
            for (int j = 0; j < MAX_CHAR1; j++)
                xsum1 /= fact1[freq1[j]];
            sum1 += xsum1;
            // sum1 >= n1の場合、その文字を
            // 現在位置の文字として確定し、
            // sum1と必要なn番目の値を更新
            if (sum1 >= n1) {
                out1[k1++] = i + 'a';
                n1 -= (sum1 - xsum1);
                break;
            }
            // sum1 < n1の場合、文字を戻す
            if (sum1 < n1)
                freq1[i]++;
        }
    }
    // sum1 == n1の場合、この文字が
    // 最大の順列としてn番目の順列を
    // 提供することを意味する
    for (int i = MAX_CHAR1 - 1;
        k1 < len1 && i >= 0; i--)
    if (freq1[i]) {
        out1[k1++] = i + 'a';
        freq1[i++]--;
    }
    // 文字列終端文字を追加して
    // 結果を出力
    out1[k1] = '\0';
    cout << out1;
}
// ドライバープログラム
int main(){
    int n1 = 5;
    char str1[] = "tutorialspoint";
    // int n1 = 3;
    // char str1[] = "pqr";
    //int n1 = 2;
    //char str1[] = "xyx";
    nPermute(str1, n1);
    return 0;
}

出力結果

aiilnooprtsttu