Project Euler Problem 024

http://projecteuler.net/index.php?section=problems&id=24
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2024

A permutation is an ordered arrangement of objects.
For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4.
If all of the permutations are listed numerically or alphabetically,
  we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
  012   021   102   120   201   210
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

0から9までの数字を使って10桁の数字を作る。それを辞書順に並べた時(数字なんで普通に並べた時)の100万番目の数は調べる。

Pythonでは順列を扱うには itertools の permutations が使える。順番に調べて100万番目の値を調べればよい。

import itertools
import datetime

def euler024a():
    N = 1000000

    result = []
    i = 0
    for x in itertools.permutations(range(10), 10):
        i += 1
        if i == N:
            result = x
            break
    print reduce(lambda a, b: a * 10 + b, result)


begin = datetime.datetime.now()
euler024a()
end   = datetime.datetime.now()
print end - begin

答え: 2783915460
実行時間: 0.290858秒くらい

ひと工夫

最初のやりかたは、順列を全部調べるので効率が悪い。なので工夫する。説明は超てきとう。

例えば最初の数字が 0 の場合の組み合わせの数は、9! で 362880 となり、1000000 以下なので、最初の数字は 0 では無い事がわかる。
最初の数字が 1 のとき(9! * 2 = 725760)でも 1000000 に満たないので 1 でもない。同じように調べると、最初の数字が 2 である事がわかる。
最初の数を 2 とした場合、残りの組み合わせは 8! なので同じように調べていけば、n番目の順列をピンポイントで見つける事ができる。

import datetime

def permutation_of_index(lst, index):
    def make_fact_table(n):
        result = [ 0 ]
        a = 1
        for i in xrange(1, n):
            a *= i
            result.append(a)
        return result
    
    fact_tbl = make_fact_table(len(lst))
    fact_tbl.reverse()
    
    l = lst[:]
    
    n = index
    result = []
    for i in xrange(len(l)):
        
        id = 0
        if fact_tbl[i] and n >= fact_tbl[i]:
            id = n / (fact_tbl[i])
            n %= fact_tbl[i]
            
        result.append(l[id])
        l.pop(id)
        
    return result


def euler024b():
    N = 1000000
    result = permutation_of_index(range(10), N-1)
    print reduce(lambda a, b: a * 10 + b, result)


begin = datetime.datetime.now()
euler024b()
end   = datetime.datetime.now()
print end - begin

答え: 2783915460
実行時間: 0.000051秒くらい

だいぶん、早くなった！