ヽ|∵|ゝ(Fantom) の 開発blog? ホーム » Ruby »【Ruby】階乗・順列・組合せの個数を求める

【Ruby】階乗・順列・組合せの個数を求める  


 配列の生成ではなく、場合の数としての個数が欲しかったので、Java と同じ factorial, permutation, combination を移植してみた。ただ、Ruby には「inject」のような便利な畳み込み計算があるので、そこだけ修正。ループで計算もやってみたが、巨大な値の計算になると実行速度は inject の方がわずかに速いようだ。手抜き(笑)で負の値や不正値のエラーなどは書いてないので、必要であれば自分で付け足して使って欲しい。

●階乗・順列・組合せの個数(オープンクラス版)
#階乗・順列・組合せの個数(オープンクラス)
class Integer
def factorial
return 1 if self == 0
(1..self).inject(:*)
end

def permutation(r)
return 1 if self == 0
s = self - r + 1
(s..self).inject(:*)
end

def combination(r)
r = [r, self - r].min
return self if r == 1
return 1 if r == 0
self.permutation(r) / r.factorial
end
end


#メインでは...
n = 6
r = 3
print "#{n}! = #{n.factorial}\n"
print "#{n}P#{r} = #{n.permutation(r)}\n"
print "#{n}C#{r} = #{n.combination(r)}\n"

6! = 720
6P3 = 120
6C3 = 20

 Java 版のときにも少し書いたが、この手の単純な計算の場合、再帰では書かない方が良いだろう。やってみればわかるが、特に combination(組合せの数) などは再帰でやると、大きな値を計算するときに非常に重くなる。オンラインジャッジではタイムアウトし兼ねないので、単純なコードの方が安全だ。

 オープンクラスで使いたくないなら、下記の通常のメソッド版でも良いだろう。Java から見ると C# の拡張メソッドなども羨ましい限りだけどね(Java8 でもインターフェイスの default 実装で同じようなことができるという話もあるが…)。確かに複数人で開発するときは、勝手に上書きされるのを嫌う人もいるかもしれない。

●階乗・順列・組合せの個数(通常のメソッド版)
#階乗・順列・組合せの個数(通常のメソッド)
def factorial(n)
return 1 if n == 0
(1..n).inject(:*)
end

def permutation(n, r)
return 1 if n == 0
s = n - r + 1
(s..n).inject(:*)
end

def combination(n, r)
r = [r, n - r].min
return n if r == 1
return 1 if r == 0
permutation(n, r) / factorial(r)
end


#メインでは...
n = 6
r = 3
print "#{n}! = #{factorial(n)}\n"
print "#{n}P#{r} = #{permutation(n, r)}\n"
print "#{n}C#{r} = #{combination(n, r)}\n"

6! = 720
6P3 = 120
6C3 = 20

 Ruby は巨大な桁になる計算でもオーバフローを気にしないでいい所が良いね。順列や組合せの個数は解法そのものに必要なくても、計算量を算出したり、おおよその答えの個数を考えたりするのに非常によく使う。私はちょっとしたコードを試したり、ネットで見つけたコードを分析したりするだけなので、Rails ではなく、Eclipse にプラグインを入れて試しているが、環境を作るのが面倒だと思ったら、「paiza.io」や「ideone」などのオンライン環境を使うのも手だ。実際に私は書いたコードをオンライン環境でよく試している(オンライン環境でタイムアウトしないコードが書ければ、オンラインジャッジは全て通過できる)。特に「paiza.io」は日本語に対応しているから使いやすいしね。使ったことない言語でも、ググって見つけたコードをすぐに試せるのでオススメだ(笑)。それにしても、いつでもオンラインで調べものも勉強も環境も簡単にできるし、いい時代になったもんだ…。最後に環境構築に役立つURLを参考に載せておこう。

(参考)
WindowsでEclipse+Ruby
eclipseでRuby開発を行ってみる
EclipseでRubyの開発環境を構築した時のメモ
Pleiades All in One - Eclipse プラグイン日本語化プラグイン

(オンラインIDE)
paiza.io
ideone


(関連記事)
【Java】組合せの数を求める
【Java】順列の数を求める
【Java】プリミティブ型での階乗計算


スポンサーサイト

category: Ruby

thread: プログラミング

janre: コンピュータ

tag: 算術関数 
tb: 0   cm: --


トラックバック

トラックバックURL
→http://fantom1x.blog130.fc2.com/tb.php/206-18ee64ae
この記事にトラックバックする(FC2ブログユーザー)

プロフィール

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop