【TIPS】Elixir で配列から要素を取り出す全ての組み合わせを取得する

はじめに

例えば [1, 2, 3, 4] という配列から 3 個の要素を取り出すとき、以下のような組み合わせが有り得ます

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

組み合わせの数は以下の公式で簡単に計算できます

$$
{}_nC_r = \frac{n!}{r!(n-r)!}
$$

しかし、実際の組み合わせを取得するには少し工夫が必要なので、 TIPS としてまとめておきます

実装したノートブックはこちら

組み合わせ取得モジュール

以下のコードが組み合わせ取得モジュールです

defmodule Combinations do
  def all(list) do
    1..length(list)
    |> Enum.reduce([], fn n, acc ->
      acc ++ all(list, n)
    end)
  end

  def all(_, 0), do: [[]]
  def all([], _), do: []
  def all(list, n) when length(list) == n, do: [list]

  def all([head | tail], n) when n > 0 do
    with_head = for combo <- all(tail, n - 1), do: [head | combo]
    without_head = all(tail, n)
    with_head ++ without_head
  end
end

やっていることは以下の処理です

• 配列の要素数 = 取り出す数の場合は必ず組み合わせが特定できる
  [1, 2] から 2 個取り出す場合、必ず [1, 2] のパターンしか存在しない
• 配列の要素数が増えたとき、取り出すパターンは以下のもので構成されている
  • 増える前の全ての組み合わせ（without_head）
    [1, 2, 3] から 2 個取り出す場合、 [1, 2] から 2 個取り出したときにあった [1, 2] のパターンは必ず含まれる
  • 増える前の配列から一つ少ない要素を取り出した時の組み合わせに増えた要素を追加した組み合わせ（with_head）
    [1, 2, 3] から 2 個取り出す場合、 [1, 2] から 1 個取り出すパターン、つまり [1] と [2] に 3 を組み合わせて [1, 3] と [2, 3] が追加される

このことを再帰的に利用すると、短い長さの組み合わせからどんどん要素を追加していくことで長い配列の場合でも全ての組み合わせが取得できます

使用例

入力の配列が以下のようなものだったとします

list = [1, 2, 3, 4]

取り出す数に 2 を指定して実行します

Combinations.all(list, 2)

実行結果

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

取り出す数に 3 を指定します

Combinations.all(list, 3)

実行結果

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

長さを指定しない場合、取り出す数についても全てのパターンを網羅します

Combinations.all(list)

実行結果

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

まとめ

再帰処理を使うことで、全ての組み合わせを取得できました

Advent of Code や AtCoder などでも活用できるので、参考にしてみてください