🍶組み合わせを列挙するアルゴリズムについて(Ruby)

この記事はQiitaの記事をエクスポートしたものです。内容が古くなっている可能性があります。

組み合わせ

Rubyで組み合わせを求める機会があった。 Rubyには便利なメソッドがあって、以下のように求めることができる。

arr = [1, 2, 3, 4, 5]
p arr.combination(2).to_a

# OUTPUT
[[1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]]

しかし、これを実際に自分で実装しようとすると意外と難しいなと感じたのでまとめてみる。

実装

考え方

直感的な考え方は、自分で樹形図を書くプロセスである。 例えば、[1,2,3,4]から3つの要素を取る組み合わせを考える。 まず、1を取る。残った[2,3,4]から2つを取ってきて1に加える。 [1,2,3][1,2,4][1,3,4]ができる。 次に、2を取る、残った[3,4]から2つ取ってきて2に加える。 [2,3,4]ができる。 合わせて、４つの組み合わせができる。 これは再帰的に実装をすることができる。

再帰終了条件 [1,2,3]から3つ取ってくるようなときは[[1,2,3]]を返す。 [1,2,3]から1つ取ってくるようなときは[[1],[2],[3]]を返す。

Rubyでは、インスタンスメソッド中でレシーバを省略するとselfが暗黙的にレシーバになる。

　コード

class Array
  # EXAMPLE: [1.2.3.4].combination_array(3) => [[1,2,3], [1,2,4], [1,3,4], [2,3,4]]
  def combination_array(comb_size)
    return [] if comb_size > size # 4C5のようなものは空を返す
    return [] if comb_size == 0 # 4C0のようなものは空を返す
    return [self] if comb_size == size
    return map { |e| [e] } if comb_size == 1

    ret = []
    (0..size - comb_size).each do |i|
      picked = self[i]
      rest = self[i + 1..-1]
      rest.combination_array(comb_size - 1).each do |c|
        ret << [picked] + c
      end
    end
    ret
  end
end

if $PROGRAM_NAME == __FILE__
  p %i[asahi kirin sapporo suntory].combination_array(2)

  # 重複がない時(既存メソッドとの比較)
  p [1, 2, 3, 4, 5, 6, 7, 8, 9].combination_array(3) == [1, 2, 3, 4, 5, 6, 7, 8, 9].combination(3).to_a

  # 重複がある時(既存メソッドとの比較)
  p [1, 2, 3, 4, 5, 6, 1, 8, 3].combination_array(4) == [1, 2, 3, 4, 5, 6, 1, 8, 3].combination(4).to_a
end

## OUTPUT
[[:asahi, :kirin], [:asahi, :sapporo], [:asahi, :suntory], [:kirin, :sapporo], [:kirin, :suntory], [:sapporo, :suntory]]
true
true

参考

https://blog.shibayu36.org/entry/2016/12/22/092511