【Project Euler】Problem 24: 辞書式順列

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 24. 辞書式順列

原文 Problem 24: Lexicographic permutations

問題の要約：0123456789を並べ替えたものを辞書式順列にしたとき$10^6$番目を求めよ

安易ですが、itertoolsのpermutationは「 iterable に応じた辞書式順序で出力されます」とのことなのでそのまま使えます。一応"012"で確認します。

import itertools
for n, perm in enumerate(itertools.permutations("012"),1): 
  print(f"{n}: {''.join(perm)}")
#1: 012
#2: 021
#3: 102
#4: 120
#5: 201
#6: 210

確認できたので、$10^6$番目の値を出力します。

import itertools
for n, perm in enumerate(itertools.permutations("0123456789"),1): 
  if n >= 10**6:
    break

print(f"Answer : {''.join(perm)}")

より効率の良い解答

さすがにこれではあまりにも安易なので問題を以下のように変更します。

問題 ２．0123456789abcdefを並べ替えたものを１６進数の辞書式順列にしたとき$10^{10}$番目を求めよ

こうなるとitertoolsのpermutationでは厳しいので工夫が必要になります。

考え方を最初の問題で説明します。最初の桁を例えば0に固定すると残りは9桁なので順列は$9!=362880$個あります。これを積算すると$10^6$番目は2で始まることが分かります。

従って2を除いた013456789を並べ替えたものを辞書式順列にしたときに$10^6-725760=274240$番目を求めて725760に足せばよいことになります。
これを再帰的に行えば答えが得られます。

最初の桁	順列の数	順列の数（積算）
0	$9!=362880$	$362880$
1	$9!=362880$	$725760$
2	$9!=362880$	$1088640 > 10^6$

以下のプログラムは１６進数まで対応できるようにしました。

import math
B = 16
def lexn(N, dig, un):  # Remaing N, digit, Unused number
  result, total = "", 0
  for i in range(B):
    if un[i] == 0: continue
    d = math.factorial(dig-1)
    if total+d >= N:
      un[i] -= 1
      result = hex(i)[2] + lexn(N-total, dig-1, un)
      return result
    total += d
  return result

N = 10**10
print(f"Answer: {lexn(N, B, [1]*B)}")
# 013ae8c5dfb47692

（開発環境：Google Colab）