fun insEverywhere e nil = [[e]]
  | insEverywhere e (y::ys) =
    (e::y::ys) :: (map (fn u => y::u) (insEverywhere e ys));

fun appendAll nil = nil
  | appendAll (z::zs) = z @ (appendAll zs)

fun perm nil = [ nil ]
  | perm (x::xs) =
    appendAll (map (insEverywhere x) (perm xs));

perm[1,2,3];