This was so close to the simple solution:
~~~{.clojure}
(defn permutations [a-seq]
  (if (empty? a-seq)
    '(())
    (apply concat (map (fn [p] (rotations (cons (first a-seq) p))) (permutations (rest a-seq)))))
~~~