C++で文字列のn番目の辞書式順列を検索します

コンセプト

小文字のアルファベットのみを含む長さmの特定の文字列に関して、辞書式順序で文字列のn番目の順列を決定するタスク。

入力

str[] = "pqr", n = 3

出力

Result = "qpr"

説明

ソートされた順序で可能なすべての順列-pqr、prq、qpr、qrp、rpq、rqp

入力

str[] = "xyx", n = 2

出力

Result = "xyx"

説明

ソートされた順序で可能なすべての順列-xxy、xyx、yxx

メソッド

ここでは、この問題を解決するためにいくつかの数学的概念を使用します。

コンセプトは以下の事実に基づいています。

• ここで、N文字（すべて異なる）によって生成された文字列の順列の総数はNです！

• ここで、N文字（この場合、文字C1の頻度はM1、C2はM2…、したがって文字Ckの頻度はMk）によって生成される文字列の順列の総数はN！/（M1！* M2！ *….mk！）。

• 繰り返しますが、

  を修正した後にN文字（すべて異なる）によって生成された文字列の順列の総数

以下の手順に従って、解決策を見つけることができます。

• 最初に、配列freq[]内のすべての文字の頻度をカウントします。

• 現在、文字列に存在する最初の最小文字から（

  のような最小のインデックスi

• freq [i]> 0）、その特定のi番目の文字を最初の文字として扱った後に可能な最大順列の数を計算します。

• この合計値が指定されたnよりも大きい場合、その後、その文字を最初の結果出力文字として設定し、freq [i]をデクリメントし、残りのn-1文字についても同じように続けます。

• 一方、カウントが必要なnよりも小さい場合は、度数分布表の次の文字を繰り返し、カウントが必須n。

上記の方法の時間計算量はO（n）、つまり文字列の長さのオーダーであることに注意してください。

例

// C++ program to print
// n-th permutation
#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];
// Shows utility for calculating factorials
void precomputeFactorials(){
   fact1[0] = 1;
   for (int i = 1; i < MAX_FACT1; i++)
      fact1[i] = fact1[i - 1] * i;
}
// Shows function for nth permutation
void nPermute(char str1[], int n1){
   precomputeFactorials();
   // Indicates length of given string
   int len1 = strlen(str1);
   // Used to count frequencies of all
   // characters
   int freq1[MAX_CHAR1] = { 0 };
   for (int i = 0; i < len1; i++)
      freq1[str1[i] - 'a']++;
      // Shows out1 string for output string
      char out1[MAX_CHAR1];
      //Used to iterate till sum equals n1
      int sum1 = 0;
      int k1 = 0;
      // We umodify both n1 and sum1 in this
      // loop.
      while (sum1 != n1) {
         sum1 = 0;
         // Verify for characters present in freq1[]
         for (int i = 0; i < MAX_CHAR1; i++) {
            if (freq1[i] == 0)
               continue;
            // Remove character
            freq1[i]--;
            // Compute sum1 after fixing
            // a particuar char
            int xsum1 = fact1[len1 - 1 - k1];
            for (int j = 0; j < MAX_CHAR1; j++)
               xsum1 /= fact1[freq1[j]];
               sum1 += xsum1;
            // Now if sum1 > n1 fix that char as
            // present char and modify sum1
            // and required nth after fixing
            // char at that position
            if (sum1 >= n1) {
               out1[k1++] = i + 'a';
               n1 -= (sum1 - xsum1);
               break;
            }
            // Now if sum1 < n1, add character back
            if (sum1 < n1)
               freq1[i]++;
         }
      }
      // Now if sum1 == n1 means this
      // char will provide its
      // greatest permutation
      // as nth permutation
      for (int i = MAX_CHAR1 - 1;
         k1 < len1 && i >= 0; i--)
      if (freq1[i]) {
         out1[k1++] = i + 'a';
      freq1[i++]--;
   }
   // Used to append string termination
   // character and print result
   out1[k1] = '\0';
   cout << out1;
}
// Driver program
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