これは閃きましたわぁ（ﾄﾞﾔｧ
Problem 24 「辞書式順列」
順列とはモノの順番付きの並びのことである. たとえば, 3124は数 1, 2, 3, 4 の一つの順列である. すべての順列を数の大小でまたは辞書式に並べたものを辞書順と呼ぶ. 0と1と2の順列を辞書順に並べると
012 021 102 120 201 210
になる.
0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目はいくつか?
def hoge(num):
numbers = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
ans = ''
# 階乗の計算関数を定義
f = lambda n: n * f(n-1) if n != 0 else 1
# 総組み合わせ数（10!=3628800通り）より大きい数字の場合は即終了
if num > f(len(numbers)):
return
# i = 9 → 1 でループ
for i in xrange(len(numbers)-1, 0, -1):
# 最初の数字を固定した場合の組み合わせ数を算出する
# 最初のループではi=9のため9!通り
combi_cnt = f(i)
# このif分は2ループ目以降に通る
if num == 0:
ans += numbers.pop(-1)
continue
# 以下の計算でx+1番目の数字で始まるnum番目の数字が答えとなることが分かる
# 最初のループでは x=2, num=274240 となるため、2で始まる274240番目が答えとなる
# (num=0の場合はx番目の数字で始まる最後の組み合わせ)
x, num = divmod(num, combi_cnt) # 商と余りがとれるdivmodを最近知った
if num != 0:
ans += numbers.pop(x) # listのindexは0からなのでちょっと気持ち悪いけどx+1ではなくx
else:
ans += numbers.pop(x-1)
# 以降、同様にループしつつ1文字ずつ確定させていく
# 最後に残った数字を付け加えて返却
return ans + numbers[0]
print hoge(1000000)
itertools使っちゃいなよ、という甘い囁きが何度も脳内を駆け巡ってた。
頭の体操が目的なので出来るだけ便利系ライブラリは使わない方針です（今のところ）。