Rubyでの順列、組み合わせ。

Rubyでは「順列」と「組み合わせ」をArrayクラスのcombinationメソッドとpermutationメソッドを用いることで、簡単に求めることができます。

array = [1,2,3,4]

p array.combination(3).to_a

[[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]

combinationの引数は選び出す要素の個数を指定する。

array = [1,2,3]

p array.permutation(3).to_a

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

両方とも便利なメソッドです。

また、要素の重複を許可する場合は repeated_combination や repeated_permutation が利用できます。

なぜかIntegerクラスに存在しない

Arrayクラスには「順列」「組み合わせ」メソッドが存在するのですが、なぜかIntegerクラスには存在しません。なので単純な組み合わせの個数や順列の個数を求めようとすると。Array.countメソッドを使用する必要があります。

array = [1,2,3,4,5]

p array.permutation(3).to_a.count # n_P_k
p array.combination(3).to_a.count # n_C_k

60
10

小さい値だとそこまで影響はしませんが、内部の処理的には配列のパターンを全て列挙しているので、大きな値になってくると時間がかかってしまいます。

array = (1..20).to_a

p array.permutation(5).to_a.count # n_P_k
p array.combination(5).to_a.count # n_C_k

1860480
15504
ruby array.rb  1.14s user 0.11s system 99% cpu 1.257 total

1秒近く実行時間を費やしている。

array = (1..30).to_a

p array.permutation(5).to_a.count # n_P_k
p array.combination(5).to_a.count # n_C_k

17100720
142506
ruby array.rb  11.55s user 0.83s system 99% cpu 12.389 total

要素を10個増やしただけで実行時間がほぼ10倍近く増加。

・無いなら作る

ということでIntegerクラスをオープンして「combination」「permutation」「factorial」メソッドを定義。

class Integer
  def combination(k)
    return 1 if k.zero?

    (self - k + 1..self).inject(:*) / k.factorial
  end

  def permutation(k)
    return 1 if k.zero?

    (self - k + 1..self).inject(:*)
  end

  def factorial
    return 1 if self.zero?

    (1..self).inject(:*)
  end
end

puts "3.factorial => #{3.factorial}"
puts "0.factorial => #{0.factorial}"
puts "10.factorial => #{10.factorial}"
puts "4.combination(1) => #{4.combination(1)}"
puts "4.combination(0) => #{4.combination(0)}"
puts "10.combination(5) => #{10.combination(5)}"
puts "3.permutation(2) => #{3.permutation(2)}"
puts "20.permutation(5) => #{20.permutation(5)}"
puts "20.combination(5) => #{20.combination(5)}"

3.factorial => 6
0.factorial => 1
10.factorial => 3628800
4.combination(1) => 4
4.combination(0) => 1
10.combination(5) => 252
3.permutation(2) => 6
20.permutation(5) => 1860480
20.combination(5) => 15504

実行時間も大幅に改善されました。