Permutations in Elixir

Generate all the permutations of a given list

2023-09-24
elixir

While working on a problem, suddenly I had the need to get a hold of all the permutations of the elements in a list.

Thus, I did what any good engineer would do: I browsed the internet for a little bit and found a solution.

It makes use of for comprehensions and recursion.
It’s very concise and elegant, judge yourself:

defmodule Util do
  def permutations([]), do: [[]]

  def permutations(list) do
    for(item <- list, rest <- permutations(list -- [item]), do: [item | rest])
  end
end

For an input like this:

Util.permutations([1, 2, 3])

It’ll return this:

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

With repetition

Here is the implementation for generating permutations with repetition:

defmodule Util do
  def permutations_with_repetition(list) do
    permutations_with_repetition(list, length(list))
  end

  defp permutations_with_repetition(_list, 0), do: [[]]

  defp permutations_with_repetition(list, l) do
    for(item <- list, rest <- permutations_with_repetition(list, l - 1), do: [item | rest])
  end
end

For this input:

Util.permutations_with_repetition([1, 2, 3])

It’ll generate:

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

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

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

References