【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】プリミティブ型での階乗計算