【TIPS】Elixir で配列から要素を取り出す全ての順列を取得する

はじめに

例えば [1, 2, 3, 4] という配列から 3 個の要素を取り出して並べる場合、以下のような並び（順列）が有り得ます

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

順列の数は以下の公式で簡単に計算できます

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

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

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

順列取得モジュール

以下のコードが順列取得モジュールです

defmodule Permutations 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) do
    for x <- list,
        rest = list -- [x],
        perm <- all(rest, n - 1),
        do: [x | perm]
  end
end

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

• 配列の要素数が 1 の場合、順列も一つしか存在しない
  [1] の順列は [1] のみ
• 配列の要素数が 2 の場合、要素のうちどちらが先頭になるかで二つの順列が存在する
  [1, 2] の順列は [1, 2] と [2, 1]
• 配列の要素数が 3 の場合、先頭以外の要素でできる順列に先頭要素をつけた順列が存在する
  [1, 2, 3] の順列を考えると、以下の手順で全ての順列が作成できる
  • [2, 3] の順列 [2, 3] と [3, 2] それぞれに 1 を追加し、 [1, 2, 3] と [1, 3, 2] ができる
  • [1, 3] の順列 [1, 3] と [3, 1] それぞれに 2 を追加し、 [2, 1, 3] と [2, 3, 1] ができる
  • [1, 2] の順列 [1, 2] と [2, 1] それぞれに 3 を追加し、 [3, 1, 2] と [3, 2, 1] ができる

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

使用例

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

list = [1, 2, 3, 4]

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

Permutations.all(list, 2)

実行結果

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

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

Permutations.all(list, 3)

実行結果

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

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

Permutations.all(list)

実行結果

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

まとめ

再帰処理を使うことで、全ての順列を取得できました

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