« Project Euler - Problem 23 | トップページ | Project Euler - Problem 25 »

2009年7月 2日 (木)

Project Euler - Problem 24

問題はこちらをご覧ください。


順列といえば "permutation" ということで、こんなコードを書いてみました。

require 'math_tool' Index = 100_0000 (0 .. 9).to_a.permutation.each_with_index do |arr, i| if i + 1 == Index then puts arr.to_i break end end

これでもそこそこ速いんですが、"permutation" は律儀にすべての順列を当たってくれるので、今回のように「100 万番目だけを知りたい」といった場合には、少々無駄な処理をしています。

そこで、「n 番目」だけを知るためのコードを書いてみました。

require 'math_tool' Index = 100_0000 class Array # * 配列 arr を順列として並び替えた時の n 番目を返す。 def permutation_count(n) n = n - 1 arr = Array.new(self) ans = Array.new until arr.empty? a = (arr.size - 1).permutation_size q, n = n.divmod(a) ans.push(arr.delete_at(q)) end return ans end end puts (0 .. 9).to_a.permutation_count(Index).to_i

この方法だと、Ruby 1.9 で約 0.05 秒ほどで答が出ます。


※自作の "math_tool.rb" に関してはこちらをご覧ください。

« Project Euler - Problem 23 | トップページ | Project Euler - Problem 25 »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/45514192

この記事へのトラックバック一覧です: Project Euler - Problem 24:

« Project Euler - Problem 23 | トップページ | Project Euler - Problem 25 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ