Project Euler Problem 24

しばらく放置していたのを微妙に再開。

Problem 024。

問題は、

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

ということである。0〜9の10個の数字の順列を辞書順に並べ替えたときに、１００万個目の文字列は何か？という問題だ。

以下解答。

辞書順にならべるのであるから、まずは先頭に０が来るものから始まるのは明らかだ。先頭に０が来るものは 9! = 362880個あるわけだから、１００万個目まではまだ先がある。実際、1000000 / 362880 = 2 だから、先頭が0,1ではまだ100万個には達せず、先頭が2の途中で100万個に達することがわかる。よって、先頭の数字は2である。

すると、先頭の数字２を除いて、9個の数字からなる順列の、1000000 % 9! = 274240 番目は何か、という問題に帰着する。

これを再帰的に繰り返せば、自動的に解けるはずだ。

def fact(n):
    r = 1
    for i in range(2, n+1): r *= i
    return r

def sub(chars, nth):
    if len(chars) == 0: return ""

    l = len(chars)
    f = fact(l-1)

    chars2 = chars[:]
    c = chars2.pop( nth / f)

    return str(c) + sub(chars2, nth % f)


print sub(range(0,10), 1000000-1) # 問題では1番目を最初としているので、0始まりにするために1を引く