How can I get permutations of a list in Elixir?
Eg, for ["a", "b", "c"]
, I would expect:
# [["a", "b", "c"], ["a", "c", "b"],
# ["b", "a", "c"], ["b", "c", "a"],
# ["c", "a", "b"], ["c", "b", "a"]]
How can I get permutations of a list in Elixir?
Eg, for ["a", "b", "c"]
, I would expect:
# [["a", "b", "c"], ["a", "c", "b"],
# ["b", "a", "c"], ["b", "c", "a"],
# ["c", "a", "b"], ["c", "b", "a"]]
Like this:
defmodule Permutations do
def of([]) do
[[]]
end
def of(list) do
for h <- list, t <- of(list -- [h]), do: [h | t]
end
end
def of([]), do: [[]]
and 2.) the tail of a list would usually be pattern matched off not done via list -- [h]
You would probably also decompose the list into head/tail in the arguments like so: def of([h|t] = list) do
Nov 18 '15 at 13:24
There's a slightly different approach, it also supports specifing the desired length for the result lists:
defmodule Permutations do
def shuffle(list), do: shuffle(list, length(list))
def shuffle([], _), do: [[]]
def shuffle(_, 0), do: [[]]
def shuffle(list, i) do
for x <- list, y <- shuffle(list, i-1), do: [x|y]
end
end
Running:
iex(24)> Permutations.shuffle ["a", "b", "c"]
[["a", "a", "a"], ["a", "a", "b"], ["a", "a", "c"], ["a", "b", "a"],
["a", "b", "b"], ["a", "b", "c"], ["a", "c", "a"], ["a", "c", "b"],
["a", "c", "c"], ["b", "a", "a"], ["b", "a", "b"], ["b", "a", "c"],
["b", "b", "a"], ["b", "b", "b"], ["b", "b", "c"], ["b", "c", "a"],
["b", "c", "b"], ["b", "c", "c"], ["c", "a", "a"], ["c", "a", "b"],
["c", "a", "c"], ["c", "b", "a"], ["c", "b", "b"], ["c", "b", "c"],
["c", "c", "a"], ["c", "c", "b"], ["c", "c", "c"]]
iex(25)> Permutations.shuffle ["a", "b", "c"], 2
[["a", "a"], ["a", "b"], ["a", "c"], ["b", "a"], ["b", "b"], ["b", "c"],
["c", "a"], ["c", "b"], ["c", "c"]]
Here's a version without comprehensions:
defmodule Permute do
def permute(_chars, building, 0) do
[building]
end
def permute(chars, building, dec) do
Stream.map(chars, fn char -> building ++ [char] end)
|> Enum.flat_map(fn building -> permute(chars, building, dec - 1) end)
end
end
Useful to have a helper function to allow the input as a string too:
def permute(str) do
permute(String.split(str, "", trim: true), [], String.length(str))
end
I’d put this code here for the sake of discoverability.
defmodule P do
defmacro permutations(l, n) do
clause =
fn i -> {:<-, [], [{:"i#{i}", [], Elixir}, l]} end
return =
Enum.map(1..n, fn i -> {:"i#{i}", [], Elixir} end)
Enum.reduce(1..n, return, fn i, acc ->
{:for, [], [clause.(i), [do: acc]]}
end)
end
end
defmodule T do
require P
def permute3(list), do: P.permutations(list, 3)
end
It uses plain AST to return the nested list comprehensions.
T.permute3 ~w|a b|
#⇒ [
# [[["a", "a", "a"], ["b", "a", "a"]],
# [["a", "b", "a"], ["b", "b", "a"]]],
# [[["a", "a", "b"], ["b", "a", "b"]],
# [["a", "b", "b"], ["b", "b", "b"]]]
# ]
It would require more effort to make it possible to pass n
through as a parameter, because of early Range
expansion, but it’s still doable.
I (re)wrote this to better understand the answer above:
def permutations(list) do
if list == [] do
[[]]
else
# recursively call itself on every element picked on the list and the remaining ones
for h <- list, t <- permutations(list -- [h]) do
[h | t]
end
end
end
it works by recursion, if the list is empty return a list containing only the empty list (the only possible permutation of an empty list).
If the list is not empty, iterates over every element h
of it and calls itself with the remaining ones. Then, for every result builds the concatenated list.
A thing that confused me a bit was the way Elixir evaluates the for
with multiple ranges, I can't find it in the official documentation but it seems it evaluates the first value and the result can be used in the second. For example this is valid:
for a <-1..3, b <- 1..a*2 do
"#{a} - #{b}"
end```
Stream
s: hexdocs.pm/formulae/Formulae.Combinators.html#content