Rubyの配列で組み合わせを列挙する（翻訳）

Rubyの配列で組み合わせを列挙する（翻訳）

Rubyの配列には、さまざまな問題を解決するのに役立つ振る舞いがぎっしり詰まっています。本記事では、「配列の配列」で可能なすべての組み合わせを評価する方法を2通り見ていくことにします。

🔗 はじめに

この間、限られた時間の中で、ささやかながらRubyの技術調査を行い、つらい思いをしました。振り返ってみると、「配列の配列」から派生する組み合わせを列挙する方法の調査に時間をかけすぎていました。

調査が終わった後もこの点に未練が残っていたので、トラウマを克服するためにこの概念を本記事にまとめることにしました。皆さんも私の旅に参加してみませんか？

問題

[[5,6], [7], [8,9]]のような「配列の配列」が与えられたときに、外側の配列の要素となる各配列から1個ずつエントリを取り出して作成できる組み合わせを重複のない形で返す必要があります。

[5, 7, 8]は、そうした組み合わせの1つであることはすぐわかります。1番目の配列から5を取り出し、2番目の配列から7を取り出し、3番目の配列から8を取り出しているわけです。

[5, 7, 9]という組み合わせもありです。
既におわかりかと思いますが、実は2番目の配列はどの解でも7になります。2番目の配列には他の選択肢がないからです。

この場合は、可能な組み合わせが4つしかないので、すべての組み合わせを列挙するのは簡単です。

[5, 7, 8]
[5, 7, 9]
[6, 7, 8]
[6, 7, 9]

このタスクは、こういう小規模なケースならすぐ終わりますが、必要なのは、配列の要素数やサブ配列の要素数にかかわらず、全組み合わせを求めるメソッドなのです。既に良い方法を思いついた方もいらっしゃるかもしれませんので、よろしければ先に進む前に自分でやってみるとよいでしょう。

終わりましたか？了解です。本記事では、簡単な方法とそうでない方法の2種類をご紹介したいと思います。

🔗 1. 簡単な方法

ArrayのAPIについて私より詳しい方でしたら、Array#productという配列メソッドを既に知っていて、この作業をあっさり完了できるでしょう。私はこのメソッドをよく知らなかったばかりに、同じことを手作業でやろうとしてかなりの時間を溶かしてしまいました（なお、手作業の方法は結局失敗しました）。

最終的にArrayのドキュメントを調べることを思いつき、この作業を支援するツールを探して以下の美しいメソッドに出会ったのです。

RubyドキュメントArray#productより

数学に興味があれば、これが線形代数でいうところ外積（直積）であることにお気づきかもしれませんね。さまざまなメソッド呼び出しの結果を見て仕組みを調べてみましょう。

>> [1].product([2,3])
=> [[1, 2], [1, 3]]
>> [1,2].product([3,4])
=> [[1, 3], [1, 4], [2, 3], [2, 4]]
>> [1,2].product([3,4], [5,6])
=>
[[1, 3, 5],
 [1, 3, 6],
 [1, 4, 5],
 [1, 4, 6],
 [2, 3, 5],
 [2, 3, 6],
 [2, 4, 5],
 [2, 4, 6]]
>> [5,6].product([7], [8,9])
=> [[5, 7, 8], [5, 7, 9], [6, 7, 8], [6, 7, 9]]

コード例の最後の行は、まさに本記事の冒頭で評価した問題をシンプルに再現しています。このツールを使えば一瞬で答えを得られます。
ここで必要なのは、第1の配列を取り出し、第2以降の残りの配列を引数にして、取り出した第1配列に対してproductメソッドを実行することだけです。

def easy_combinations(array_of_arrays)
  array_of_arrays[0].product(*array_of_arrays[1...])
end

puts easy_combinations([[5, 6], [7], [8, 9])   # 戻り値: [[5, 7, 8], [5, 7, 9], [6, 7, 8], [6, 7, 9]]

def easy_combinations(array_of_arrays)
  array_of_arrays.first.product(*array_of_arrays.drop(1))
end

🔗 遠回りな方法

私が例の技術評価で心残りだったのは、Array#productにたどり着くのに時間がかかったことではなく、手作りの方法を時間切れで諦めざるを得なかったことでした。今度は最後までやってみます。

ここでは、ステップバイステップで答えを出す方法を検討することにします。冒頭で提示したシンプルな[[5, 6], [7], [8, 9]]をここでも使うことにしましょう。

最初に、最も右側の配列[8, 9]を2つの「中間解」に分割し、[8]と[9]を得ます。
次は、右から2番目の配列[7]に進み、それを上の中間解に落とし込んで[7, 8]と[7, 9]を得ます。
次は、さらに左の配列、つまり冒頭の[5, 6]に進み、それを上の中間解に落とし込んで[5, 7, 8], [5, 7, 9], [6, 7, 8]と[6, 7, 9]を得ます。

ここまでの作業を図に描いてみました。

このパターンを以下の関数に落とし込む形でソリューションを構築します。

def combinations(array_of_arrays)
  array_of_arrays.reverse.reduce([[]]) do |solutions, arr|
    cross_product(arr, solutions)
  end
end

この関数は、配列の配列を後ろから逆順に反復し、reduceで解を蓄積します。なお、Array#reduceメソッドをご存じない方向けに申し上げておくと、このメソッドはEnumerableモジュールにあります。reduceは初期値（ここでは空の[[]]）を受け取って、配列に対してブロックを実行し、その配列の次の項目と蓄積した値を合わせたものを得ます。

このブロック内で呼び出しているcross_productメソッドはまだ実装していません。このメソッドに、現在処理中のサブ配列と、これまで蓄積した解を渡します。

このcross_productメソッドは、上で図示した展開を実行します。arrの各要素を既存の解のセットに展開して、更新された解のセットを返す必要があります。cross_productメソッドの実装は以下のような感じになります。

def cross_product(arr, array_of_arrays)
  products = []
  arr.each do |elem|
    array_of_arrays.map do |array|
      products.push(array.clone.unshift(elem))
    end
  end
  products
end

コードを健全にするため、cross_productメソッドに渡されたものは改変しないことにしました。そこで、更新済みの解のセットを保存するproducts変数を導入しました。メソッドの終端ではこの変数を返します。

処理中の配列arr内にある各要素について、既存の解のセットをループで回して解を複製し、その要素を配列の冒頭に配置します。続いて、更新された解のセットをproducts配列に押し込みます。

reduceを使うことで、一度に1個の配列を展開する処理を反復して解のセットをビルドしていることがわかります。各ステップでは、更新された解のセットをcross_productメソッドに渡し、次のサブ配列を使ってさらに展開します。

新たに手作りしたこの組み合わせ生成メソッドを、上述のArray#productによる「簡単な」方法と見比べてみましょう。

class CombinationsTest < Minitest::Test

  def cases
    [
      [[0,1],[2,3],[4,5]],
      [[1,2,3],[5],[6]],
      [[0,1,2],[3,4],[5,6,7]]
    ]
  end

  def test_combinations
    cases.each do |test_case|
      assert combinations(test_case).sort == test_case[0].product(*test_case[1..]).sort
    end
  end
end

このコードと単体テストは小さなgistで公開しています。

🔗 まとめ

プログラマーなら、独創的な解法を考案したいと思うものです。通常なら、車輪の再発明を避けるために既存のソリューションに頼るべきですが、自分でアルゴリズムに取り組むことで知見と満足を得られることもあります。

本記事では、「配列の配列」が与えられたときに生成可能な組み合わせを列挙する方法を2通り説明しました。最初の方法はArray#productメソッドを使う方法で、2番目の方法はArray#reduceメソッドを反復処理することで解のセットを構築しました。

お読みいただきありがとうございます。この記事がお役に立ちましたら、元記事末尾のフォームでメールマガジンの購読いただくことで今後公開される最新記事を配信いたしますので、どうぞご検討をお願いします。

🔗 参考情報

1. RubyのArray#productメソッド
2. 本記事で扱ったコードのGitHub gist
3. Wikipedia 外積
4. RubyのArray#reduceメソッド

関連記事

Ruby: クラスメソッド内でprivateメソッドを動的に定義するときの注意（翻訳）

Rails: default_roleというクラスメソッド名は避けるべき（翻訳）