Project Euler with Ruby on WSL [Problem 24]

Project Euler Programming ruby

では

やっていきましょう

問題

Lexicographic permutations

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,1,2 なら以下の通り

012 021 102 120 201 210

0 ～ 9 の数字からなる辞書式順列の 100万番目*1の要素を答えよ(

解答方針

  • まず先頭の文字を辞書順に選び
  • 残った文字をまた辞書順に選び

と再帰的に実行すると生成できそう。

SystemStackError (stack level too deep)

。。。ダメでした。 stack overflow したわ… うーん。数が少ないといけるんだけど。 あ、0～8 でも動くわ。。。

えーい汚いけど部分列を記憶しよう

。。。ダメでした。解決しない えーいもっと汚いけど 3 個の場合も自力で展開しよう…。

これもだめだ。 stack overflow とでてるけど多分本質的にはメモリが足らん。

解答方針2

根本的に考え方を切り替える。

n 個の要素からなる辞書式順列の、k 番目(0始まり)が、 n-1 個のループのそれぞれで何番目の添え字か？ を計算することにする。

例えば [0,1,2,3] は 4! = 24通りある。 ここで、かりに k = 20 とする。 (4-1)! = 3! = 6 なので、24 は 6 回ループ x 4 である。

k / 6 = 3 だから、最上位は 4 番目(つまり3) k % 6 = 2 だから、6! パターンのうちの 2 番目(0始まり)で、 これは 2/ (2!) = 1 から第2グループの先頭だとわかる

結局 [0,1,2,3] を並べたとき 20 番目は [3, 1, 0, 2] だとわかる。(判明した添え字の要素を順番に取り除けばよい)

なお最後に自分で注意していた100万番目 1スタートですね に見事に引っかかった

*1:1スタートですね