Project Euler 024を解いてみる。「辞書式順列」

# Project Euler 024
[024](http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2024)
>順列とはモノの順番付きの並びのことである. たとえば, 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万番目はいくつか?


->[次の問題](https://qiita.com/radiol/items/868e5cafe333a1a3c21c)

## 考え方
itertoolsを用いて順列を1個目から順番に出して行く方法もありますが、要素が増えると加速度的に計算量が増えてしまいます。

今回、要素数が増えても計算量があまり増えない方法を考えつきました！アルゴリズムは自信作です(*´ω｀*)

まず、今回の例では組み合わせは全部で`10!=3628800通り`あります。
では、先頭が0から始まる組み合わせはいくつあるでしょうか。0を除いた1~9の9個の組み合わせなので`9!=362880通り`です。同様に1から始まるものや2から始まるものも362880通りあります。
0から始まるものが36万2880通り、1から始まるものが36万2800通り、2から始まるものが36万2800通りあり、順番に並んでいるということは`100万番目は2から始まる組み合わせの中にある`ということがわかります。
![図1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/346690/98f77350-43c9-5246-b7c6-4c3551efad21.png)

先頭2が確定したということで、次に20から始まるものはいくつあるかと考えると、残った8個の数字の組み合わせなので`8!=40320通り`あります。同様に21から始まるものは40320通り、23から始まるものも40320通りあります。
0または1で始まるものは362880×2=725760通りあるので100万番目の要素は`2から始まる要素の中では100万-72万4760=27万4240番目`にあります。
20,21,23,24,25,26それぞれで始まるものは`40320×6= 241920個`あり、`2から始まる36万2800通りのうち、27万4240番目の要素は27から始まる`ということがわかります。
![図2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/346690/ec52fc7d-2844-cb38-08b8-7927555a0c11.png)

これを繰り返していくことで100万番目の配列を導くことができます。

まとめると10!通りのX番目の要素を調べたい場合、先頭はX/9!の商が先頭の数字、次にX/9!の余りをYとし、残った要素のうち[Y/8!の商]番目の要素が2番目の数字、あとは7!、6!…と繰り返していけば組み合わせを全て出さなくても特定の部分の要素を出すことができます。

## コード
```Python:euler024.py
from math import factorial


def main():
    n = 10 ** 6  # n=100万
    n = n - 1  # 処理が0 = 1番目、1 = 2番目とn-1=n番目に対応しているので1を引く
    num_list = list(range(10))  # [0,1,2,3,4,5,6,7,8,9]を作成
    factorical_list = [factorial(i) for i in range(len(num_list))]  # 階乗のリストを作成 factorical_list = [0,1!,2!,3!,4!,5!,6!,7!,8!,9!]
    ans = '' #答え用の変数
    for f in reversed(factorical_list):  # 階乗のリストを逆順にfへ代入
        ans += str(num_list.pop(n // f))  # nをfで割った商のindexにある数字をansの後ろに付け加える
        n = n % f  # n/fの余りを新たなnとする
    print(ans)


if __name__ == '__main__':
    from time import time as t
    st = t()
    main()
    print(t() - st, 'sec')
```
[paiza](https://paiza.io/projects/new)にて実行
`結果
2783915460
2.002716064453125e-05 sec
`
このアルゴリズムであれば、0~9及びA~Zのアルファベットを含めた36個の要素の順列 `37正1993澗3267溝8990穣1217𥝱4679垓9944京8150兆8352億通り`から`10正(10の41乗)番目`の要素を導くことも一瞬でできます。

```Python:euler024.py
from math import factorial


def main():
    n = 10 ** 41  # n=10正番目
    n = n - 1  # 処理が0 = 1番目、1 = 2番目とn-1=n番目に対応しているので1を引く
    num_list = list(range(10))  # [0,1,2,3,4,5,6,7,8,9]を作成
    alphabet = [chr(i) for i in range(ord('A'), ord('A') + 26)]
    num_list.extend(alphabet)  # アルファベットを要素に追加
    factorical_list = [factorial(i) for i in range(len(num_list))]
    # 階乗のリストを作成 factorical_list = [0,1!,2!,3!,4!,5!,6!,7!,8!,9!]
    ans = '' #答え用の変数
    for f in reversed(factorical_list):  # 階乗のリストを逆順にfへ代入
        ans += str(num_list.pop(n // f))  # nをfで割った商のindexにある数字をansの後ろに付け加える
        n = n % f
    print(ans)

if __name__ == '__main__':
    from time import time as t
    st = t()
    main()
    print(t() - st, 'sec')
```

0~9,A~Zの36個の要素組み合わせの10<sup>41</sup>番目
`9OQC2FWGZJRBVNEPX3871U5YASKHLMT4D6I0
4.1484832763671875e-05 sec
`
ずっと力押しの解答が続いていた中で今回はきれいに解けたし、コードも与える配列とnを変更すればいろいろな組み合わせが出せて汎用性があり、満足です(*´ω｀*)