The community on StackOverflow seems not convinced, but I wave my flag for this implementation written by Nathan Long on StackOverflow.

As list comprehension is implemented in Elixir (with for/1). And list comprehension is the right logic for the job.

defmodule Permutations do
  def of([]), do: [[]]
  def of(list), do: for h <- list, t <- of(list -- [h]), do: [h | t]

No need for recursions and pattern matched function calls.