Project Euler 24 別解

Q24.
0〜9の並び替えからなる数を辞書順に並び替えたときの100万番目の数

最上位桁を決めると残りは9!=362880だから、
999999 ÷ 9! = 2 … 274239
ということは、最上位桁は2で決まりである。2を除いた数字で以下同じことを繰り返す。

N = 1000000
def factorial(n):

    if n == 0:

        return 1

    else:

        return n * factorial(n - 1)
def get_nth(a, n):

    if n == 0:

        return a

    else:

        length = len(a)

        f = factorial(length - 1)

        i = n / f

        b = a.pop(i)

        return [ b ] + get_nth(a, n - i * f)
a = get_nth(range(10), N - 1)

print "".join(map(str, a))