Pythonで文字列のn番目の辞書式順列を検索する

長さがmの文字列があり、この文字列に小文字のみが含まれているとすると、辞書式順序で文字列のn番目の順列を見つける必要があります。

したがって、入力がstring ="pqr"、n =3の場合、すべての順列が[pqr、prq、qpr、qrp、rpq、rqp]であるため、出力は "qpr"になり、並べ替えられた順序になります。

これを解決するには、次の手順に従います-

• MAX_CHAR：=26

• MAX_FACT：=20

• 階乗：=サイズMAX_FACTの配列

• 階乗[0]：=1

• 1からMAX_FACTの範囲のiの場合、実行

  • factorials [i]：=factorials [i-1] * i

• サイズ：=文字列のサイズ

• オカレンス：=サイズMAX_CHARの配列、0で埋める

• 0からサイズの範囲のiの場合、実行

  • オカレンス[ASCIIof（string [i]）-ASCII of（'a'）]：=オカレンス[ASCII of（string [i]）-ASCII of（'a'）] + 1

• res：=サイズMAX_CHARの配列

• 合計：=0、k：=0

• Sumはnと同じではありませんが、実行してください

  • 合計：=0

  • 0からMAX_CHARの範囲のiの場合、実行

    • オカレンス[i]が0と同じ場合、

      • 次のイテレーションに行く

    • オカレンス[i]：=オカレンス[i]-1

    • temp_sum：=階乗[サイズ-1-k]

    • 0からMAX_CHARの範囲のjについては、次のようにします

      • temp_sum：=temp_sum / factorials [occurrence [j]]（整数除算）

    • Sum：=Sum + temp_sum

    • Sum> =nの場合、

      • res [k]：=ASCIIコードからの文字（i + ASCII of（'a'））

      • n：=n-合計-temp_sum

      • k：=k + 1

      • ループから出てきます

    • Sum

      • オカレンス[i]：=オカレンス[i] + 1

• i：=MAX_CHAR-1

• k<サイズおよびi>=0の場合、実行

  • オカレンス[i]がゼロ以外の場合、

    • res [k]：=ASCIIコードからの文字（i + ASCII of（'a'））

    • オカレンス[i]：=オカレンス[i]-1

    • i：=i + 1

    • k：=k + 1

  • i：=i-1

• インデックス0から（k-1）までのresからmake文字列を返します

例

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

MAX_CHAR = 26
MAX_FACT = 20
factorials = [None] * (MAX_FACT)
def get_nth_permute(string, n):
   factorials[0] = 1
   for i in range(1, MAX_FACT):
      factorials[i] = factorials[i - 1] * i
   size = len(string)
   occurrence = [0] * (MAX_CHAR)
   for i in range(0, size):
      occurrence[ord(string[i]) - ord('a')] += 1
   res = [None] * (MAX_CHAR)
   Sum = 0
   k = 0
   while Sum != n:
      Sum = 0
      for i in range(0, MAX_CHAR):
         if occurrence[i] == 0:
            continue
         occurrence[i] -= 1
         temp_sum = factorials[size - 1 - k]
         for j in range(0, MAX_CHAR):
            temp_sum = temp_sum // factorials[occurrence[j]]
         Sum += temp_sum
         if Sum >= n:
            res[k] = chr(i + ord('a'))
            n -= Sum - temp_sum
            k += 1
            break
         if Sum < n:
            occurrence[i] += 1
   i = MAX_CHAR-1
   while k < size and i >= 0:
      if occurrence[i]:
         res[k] = chr(i + ord('a'))
         occurrence[i] -= 1
         i += 1
         k += 1
      i -= 1
   return ''.join(res[:k])

n = 3
string = "pqr"
print(get_nth_permute(string, n))

入力

"pqr"

出力

qpr