Pythonで1からnまでの順列のk番目の辞書式順序を見つけるプログラム

問題の概要

2つの整数 n と k が与えられたとします。ここで、1から n までの数字のリスト [1, 2, ..., n] を考え、このリストのすべての順列を辞書式順序で並べます。例えば n = 4 の場合、順列は次の24通りになります。

[1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321]

この順列の中から k 番目の値を文字列として求めるのが本記事の目的です。例えば、入力が n = 4、k = 5 の場合、出力は「1432」となります。

解き方：階乗進数（factoradic）を活用する

この問題は階乗進数（factorial number system）という記数法を使うと効率的に解けます。階乗進数では各桁の重みが階乗になっており、任意の整数を一意に表現できます。この変換結果の各桁は「残りの候補リストから何番目の要素を選ぶか」を示すため、全順列を実際に生成せずに、目的の順列を直接組み立てることが可能です。

手順1：数値を階乗進数へ変換する関数 factors()

• 関数 factors() は引数 num を受け取ります。
• quo := num と初期化します。
• res := 先頭に 0 を挿入した両端キュー（deque）を用意します。
• i := 2 とします。
• quo が空（0）でない間、次を繰り返します。
  • quo := quo ÷ i の商、rem := quo mod i を求めます。
  • rem を res の左端に挿入します。
  • i := i + 1 とします。
• res を返します。

手順2：メイン処理

• numbers := 1 から n までの値を持つリストを作成します。
• res := 空文字列とします。
• k_fact := factors(k) を計算します。
• k_fact のサイズが numbers のサイズより小さい間、次を繰り返します。
  • res := res + numbers の先頭要素（文字列化）、その後 numbers の先頭要素を削除します。
• k_fact の各 index について、次を実行します。
  • number := numbers の index 番目の要素を取り出し、リストから削除します。
  • res := res + number とします。
• res を返します。

実装例

以下は Python による実装例です。

from collections import deque

def factors(num):
    quo = num
    res = deque([0])
    i = 2
    while quo:
        quo, rem = divmod(quo, i)
        res.appendleft(rem)
        i += 1
    return res

class Solution:
    def solve(self, n, k):
        numbers = [num for num in range(1, n + 1)]
        res = ""
        k_fact = factors(k)
        while len(k_fact) < len(numbers):
            res += str(numbers.pop(0))
        for index in k_fact:
            number = numbers.pop(index)
            res += str(number)
        return res

ob = Solution()
n = 4
k = 5
print(ob.solve(n, k))

入力

4, 5

出力

1432

まとめ

階乗進数への変換を利用することで、すべての順列を列挙することなく、k 番目の辞書式順序の順列を直接構築できます。計算量はおおむね O(n²) に抑えられ、n がある程度大きくなっても高速に動作するのが大きな特徴です。