Mutative Heap's algorithm (permutations generator) in Clojure

Question

For a side project I'm working on, I need to be able to generate permutations. Instead of relying on an existing library like math.combinatorics, I decided to write my own implementation, and arbitrarily decided on Heap's Algorithm.

Example:

(permutations [1 2 3])
=> [[1 2 3] [2 1 3] [3 1 2] [1 3 2] [2 3 1] [3 2 1]]

I realized pretty quickly though that this algorithm relies heavily on the mutation of an array, and ended up giving up trying to adapt it to proper FP style.

I went to the dark side and made an implementation that relies on two atoms to function.

Now, the mutable array part seems pretty necessary to the algorithm, but I ended up needing a second atom to accumulate the permutations. I tried adapting the doseq part to a reduction or just using loop, but the recursive calls are such that it's very difficult to see how I'd pass data along back up the stack.

Mainly, I'd like advice on how I can get rid of the need for result-atom, but I'd welcome any critique here.

I'm fully aware that this is going strongly against the FP grain here, but I seemed forced into this corner trying to implement this algorithm. I'd also, if possible, like to see a fully FP implementation of this, but I'd wager that that would be quite difficult.

I'm also aware that Heap's algorithm may not be suited for FP, but that's ok. After like half an hour of fiddling, I became more focused on producing a working implementation of this algorithm, and less whether or not this was the right algorithm to be using in the first place.

(ns wof-guesser.logic.permutations)

(defn- swap-v [v i1 i2]
  (let [x (get v i1)]
    (-> v
        (assoc i1 (get v i2))
        (assoc i2 x))))

(defn- mutative-permutate [coll-atom result-atom]
  ((fn rec [n]
     (when (> n 1)
       (let [n-even? (zero? (rem n 2))
             swap-pos #(if n-even? % 0)]

         (doseq [i (range (dec n))]
           (rec (dec n))
           (swap! coll-atom swap-v (swap-pos i) (dec n))
           (swap! result-atom conj @coll-atom))

         (rec (dec n)))))

   (count @coll-atom)))

(defn permutations [coll]
  (let [v-coll (vec coll)
        col-a  (atom v-coll)
        res-a  (atom [v-coll])]
    (mutative-permutate col-a res-a)
    @res-a))

Answer 1

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,

=> (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,

=> (perms ['A 'B 'C])
([A B C] [B A C] [C A B] [A C B] [B C A] [C B A])