Pythonで文字列のn番目の辞書式順列を効率的に求める方法

長さmの文字列があり、この文字列が小文字の英字のみで構成されているとします。このとき、辞書順(辞書式順序)で並べたときのn番目の順列を求めたいという問題を考えます。

たとえば、入力が string = "pqr"、n = 3 だった場合、出力は "qpr" になります。これは、"pqr" のすべての順列を辞書順にソートすると [pqr, prq, qpr, qrp, rpq, rqp] となり、3番目が "qpr" だからです。

解決のためのアプローチ

この問題は、以下の手順で解くことができます。

1. 階乗テーブルの作成: MAX_CHAR を 26、MAX_FACT を 20 とし、factorials 配列に 0! から事前計算した階乗値を格納します(factorials[0] = 1 を起点に、factorials[i] = factorials[i-1] * i を繰り返します)。
2. 文字数のカウント: サイズ26の occurrence 配列を0で初期化し、文字列内の各文字の出現回数をカウントします(文字コードから 'a' のコードを引いた値をインデックスとして使用)。
3. 結果用配列の準備: 結果を格納する res 配列を用意し、Sum = 0、k = 0 で初期化します。
4. n番目の順列の特定: Sum が n と一致するまで以下を繰り返します。
   • Sum を 0 にリセットし、i を 0 から 25 まで走査します。
   • occurrence[i] が 0 なら次の文字へスキップします。
   • occurrence[i] を一時的に1減らし、temp_sum = factorials[size - 1 - k] を起点として、各文字の出現回数の階乗で整数除算を行うことで、「i番目の文字を選んだ場合の残りの並べ方の総数」を求めます。
   • Sum に temp_sum を加算し、Sum >= n になった時点で、その文字(chr(i + ord('a')))を res[k] に確定し、n を調整して k を1増やしてループを抜けます。
   • Sum < n の場合は occurrence[i] を元に戻し、次の文字の候補へ進みます。
5. 残りの文字を降順で埋める: i を 25 から減らしながら、まだ使われていない文字を res の後ろに降順で配置していきます。
6. 結果の返却: res の先頭から k 文字分を連結した文字列を返します。

実装例

理解を深めるために、以下のPython実装を見てみましょう。

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

アルゴリズムのポイント

この手法の核心は、重複を含む順列の総数を階乗の商で計算できる点にあります。残りの文字数がL、各文字の出現回数が c₁, c₂, … のとき、並べ方の総数は L! ÷ (c₁! × c₂! × …) で表されます。この性質を利用すれば、すべての順列を実際に生成してソートすることなく、目的のn番目の順列を直接特定できます。文字種が限られた比較的長い文字列でも効率的に動作するのが大きな利点です。