Project Euler 024

024

順列とはモノの順番付きの並びのことである. たとえば, 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万番目はいくつか?

->次の問題

考え方

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から始まる組み合わせの中にあるということがわかります。

先頭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から始まるということがわかります。

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

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

コード

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にて実行
結果
2783915460
2.002716064453125e-05 sec

このアルゴリズムであれば、0~9及びA~Zのアルファベットを含めた36個の要素の順列 37正1993澗3267溝8990穣1217𥝱4679垓9944京8150兆8352億通りから10正(10の41乗)番目の要素を導くことも一瞬でできます。

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⁴¹番目
9OQC2FWGZJRBVNEPX3871U5YASKHLMT4D6I0
4.1484832763671875e-05 sec

ずっと力押しの解答が続いていた中で今回はきれいに解けたし、コードも与える配列とnを変更すればいろいろな組み合わせが出せて汎用性があり、満足です(´ω｀)