Combinadic in Ruby: 配列からn個の要素の組合せを生成する

配列の中から指定した数の組み合わせを返すメソッド Array#c を考えてみました。Combinadic の Ruby 実装です。

使い方

array.c(n) => 配列からn個の要素を取り出す組合せの数を返します。
array.c(n) {|c| ...} => 配列からn個の要素を取り出す組合せをブロックに渡します。

実装

# combinadic.rb

class Array
  # get combinations.
  # when called without a block, returns the number of combinations.
  # when called with a block, pass each combination to the block.
  def c(n_token, &block)
    if n_token > size
      raise "combination size (#{n_token}) larger than the array size (#{size})."
    end
    if n_token < 0
      raise "combination size (#{n_token}) should not be negative."
    end
    if block == nil
      return n_combination(size, n_token)
    else
      n_combination(size, n_token).times do |i|
        yield combination(n_token, i)
      end
    end
  end

  # get the number of combinations.
  def n_combination(n_slot, n_token)
    if(n_token == 0 || n_token == n_slot)
      1
    else
      n_combination(n_slot - 1, n_token - 1) + 
        n_combination(n_slot - 1, n_token)
    end
  end
  private :n_combination

  # return the combination at index i of combinadic
  def combination(n_token, i)
    c = []
    size.times do |sl|
      break if n_token == 0
      threshold = n_combination(size - sl - 1, n_token - 1)
      if i < threshold
        c << self[sl]
        n_token -= 1
      else
        i = i - threshold
      end
    end
    c
  end
  private :combination
end

if __FILE__ == $0
  [:fruit, :rock, :flower, :glass, :book, :pipe].c(3) {|c| p c}
end

出力例

$ ruby combinadic.rb
[:fruit, :rock, :flower]
[:fruit, :rock, :glass]
[:fruit, :rock, :book]
[:fruit, :rock, :pipe]
[:fruit, :flower, :glass]
[:fruit, :flower, :book]
[:fruit, :flower, :pipe]
[:fruit, :glass, :book]
[:fruit, :glass, :pipe]
[:fruit, :book, :pipe]
[:rock, :flower, :glass]
[:rock, :flower, :book]
[:rock, :flower, :pipe]
[:rock, :glass, :book]
[:rock, :glass, :pipe]
[:rock, :book, :pipe]
[:flower, :glass, :book]
[:flower, :glass, :pipe]
[:flower, :book, :pipe]
[:glass, :book, :pipe]

感想

Combinadic を私なりに Ruby らしく実装しようとしたところ、こうなりました。他の人が実装すると、異なった実装が出てくるかもしれないと思います。Perl は statement レベルで TIMTOWTDI ですが、Ruby は statement のレベルでは TIMTOWTDI ではないものの、オープンクラスという特徴を提供するなどして、もう少し抽象度の高いレベルで TIMTOWTDI を実現しているかもしれないという感想を持ちました。

参考文献

Google ドキュメント - オンラインでドキュメントを作成/編集できる無料サービスです

Java による実装があり、combinadic.rb の作成にあたってはこれを参考にしました。

Download Visual Studio 2003 Retired Technical documentation from Official Microsoft Download Center

C# による実装があります。

[追記] この話は既出

このエントリを公開してから気がついたのですが、ほとんど同じことが 2006 年 8 月に ruby-list で議論されていることが分かりました。
組み合わせを作るrubyらしい方法 から始まるスレッドの中で、いくつか実装が出てきていて、このエントリで公開したスクリプトと似た感じの実装になっています。
このエントリの結論は、「車輪の再発明は面白い」ということにしたいと思います。