10

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"]]
1

5 Answers 5

11

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
6
  • 6
    @OnorioCatenacci That's not a very informative comment. :D I'm not an Elixir expert yet. I'd be happy to see a more idiomatic solution if you have time to post one - mostly I put this here because I thought it would be a common question but I didn't find an answer on SO. Next time I search, I will. I think of it as a "note to self" that others can also use. Nov 17, 2015 at 20:31
  • 2
    The comment wasn't really directed at you. It was more directed at others who might see your code and, not knowing any better, assume that's the right way to write Elixir code. Nov 17, 2015 at 22:08
  • So @OnorioCatenacci why is it not idiomatic? I'm also new to Elixir and would appreciate an explanation of the difference between this and the 'right way'. Thanks. Nov 18, 2015 at 11:26
  • 1
    I don't have the time to put up a more idiomatic version so here are my issues with it. 1.) def of([]) . . . would be more idiomatically written as 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, 2015 at 13:24
  • 1
    I think the issue here is looking at h/t as the head/tail of the list from the argument while they're temp variables in the for comprehension. The rosetta stone implementation (based on erlang's) uses x,y instead of h/t and may be clearer. PS: linking rosetta instead of block code here Nov 18, 2015 at 20:39
6

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"]]

Source

1
  • 2
    I'm not sure this is the desired output, there are repetitions
    – Jacopofar
    Dec 8, 2019 at 14:26
0

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
0
0

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.

0

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```

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.