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.
(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))