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個の数字の順列を辞書順に並べ替えたときに、100万個目の文字列は何か?という問題だ。
以下解答。
辞書順にならべるのであるから、まずは先頭に0が来るものから始まるのは明らかだ。先頭に0が来るものは 9! = 362880個あるわけだから、100万個目まではまだ先がある。実際、1000000 / 362880 = 2 だから、先頭が0,1ではまだ100万個には達せず、先頭が2の途中で100万個に達することがわかる。よって、先頭の数字は2である。
すると、先頭の数字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を引く