Mutative Heap's algorithm (permutations generator) in Clojure
I'd also, if possible, like to see a fully FP implementation of this,
  but I'd wager that that would be quite difficult.


Here is a functional implementation of Heap's algorithm in Clojure, based on page 12 of Robert Sedgewick's lecture (Don't look at the next page - the code is dubious).

The idea is to generate the sequence of swaps as pairs of indices. That's what the swaps function does. For an argument n, it generates n! - 1 of them: 

(defn swaps [n]
  (if (= n 1)
    ()
    (let [base (swaps (dec n))
          extras (if (odd? n) (repeat (dec n) 0) (range (dec n)))]
      (concat
        base
        (mapcat (fn [x] (cons [x (dec n)] base)) extras)))))


It interleaves the extras between n copies of the base, the sequence of swaps of n-1 elements.

For example, 

=&gt; (swaps 3)
([0 1] [0 2] [0 1] [0 2] [0 1])


The perms function ...

(defn perms [v]
  (reductions
    (fn [a [i j]] (assoc a i (a j) j (a i)))
    v
    (swaps (count v))))


... simply applies these swaps successively to its vector argument. 

For example, 

=&gt; (perms ['A 'B 'C])
([A B C] [B A C] [C A B] [A C B] [B C A] [C B A])