RubyでProject Euler - Problem 24

Problem 24 (原文)

順列とはモノの順番付きの並びのことである. たとえば, 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万番目を答えよ

本問題から問題文はProject Euler - PukiWikiにある和訳を掲載させていただきます。

電卓持ち込み可の大学入試ならそのまま出題されてもおかしくない問題です。

カード10枚を並べ替える順列の数は10!通りあります。なお、10!は「10の階乗」と読み、1*2*3*4*5*6*7*8*9*10 = 3,628,800ですから、100万番目といえども、辞書順では比較的最初の方でしょう。

これらの順列の全てを格納した配列を仮に"ary"と名づけてみます。

「１番目」は、ary[0] = "0123456789"ですね。「最終番目」は「10!番目」となり、ary[10!-1] = "9876543210" です。

では、ary[9!-1], ary[9!]は、どういった文字列になるでしょうか。

さらに、ary[2*9!]、ary[2*9!-1]についてはどうでしょう。

ここまで来れば、以下のような類推ができるでしょう。

題意にある「100万番目」、つまり999,999が下記のように表されるときの n₉, n₈,…n₁が、配列要素 ary[999,999]と密接な関わりを持つらしいということです。

999,999 = n₉ * 9! + n₈ * 8! + … + n₁ * 1!

というわけで私の書いたコードを書き込んでおきます。

カードの山から一枚を取り出す動作はメソッド"delete_at"がしっくりきます。

  # num!を返す
  def fact(num)
    return 1 if num == 0 || num == 1
    (2..num).inject(1){|ret, i|ret*=i}
  end

  def solv_24(num)
    prb = "0123456789".split(//)
    ans = []
    num -= 1
    (0..9).reverse_each do |i|
      ans << prb.delete_at((num / fact(i)).floor)
      num = num % fact(i)
    end
    ans.join
  end

  puts solv_24(100_0000)

ご注意

当分の間、トラックバックの受信を行わないことといたしました。過去に戴いたトラックバックのリストについてはそのまま保持いたします。

トラックバックはありません

コメントはありません。

ご注意

当分の間、JavaScript が有効でないとコメント投稿できないようにします。スパム対策であって、投稿される方の個人情報を取得する目的ではありません。悪しからずご了承ください。