A recursive list comprehension provides a concise way to generate every permutation of a list:
defmodule Util do
def permutations([]), do: [[]]
def permutations(list) do
for item <- list,
rest <- permutations(list -- [item]),
do: [item | rest]
end
end
The empty list has one permutation: the empty list itself. For every other input, the comprehension selects an item, recursively permutes the remaining items, and prepends the selected item to each result.
For example:
Util.permutations([1, 2, 3])
The function returns:
[
[1, 2, 3],
[1, 3, 2],
[2, 1, 3],
[2, 3, 1],
[3, 1, 2],
[3, 2, 1]
]
This implementation is intended for lists of distinct values. Repeated input values produce duplicate results. The result count also grows factorially - a list of n distinct values produces n! permutations - so use it only with small inputs.
Permutations with repetition
The following version allows every position to select any value from the original list. It generates sequences whose length equals the input list length:
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, remaining) do
for item <- list,
rest <- permutations_with_repetition(list, remaining - 1),
do: [item | rest]
end
end
For this input:
Util.permutations_with_repetition([1, 2, 3])
It generates 3³, or 27, results:
[
[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]
]