Permutations Of A String In Clojure Basic Algorithms Part Two
Jul 27, 2016 09:03 · 720 words · 4 minute read
The problem
Find all permutations of a string
The solution
My first solution is comes from Java and is a recursive solution.
(defn- perms [pre v]
(let [n (count v)]
(if (zero? n)
nil
(loop [i 0]
(if (< i n)
(do (perms (conj pre (nth v i))
(into [] (concat(first (split-at i v))
(second (split-at (inc i) v)))))
(recur (inc i)))
nil)))))
It has some problems. It is recursive so vulnerable to stack overflow errors, but more than that it is pretty slow and not very idiomatic Clojure. So I went in search of a better more idiomatic implementation of this problem and I found this.
(defn- iter-perm [v]
(let [len (count v)
j (loop [i (- len 2)]
(cond (= i -1) nil (< (v i) (v (inc i))) i
:else (recur (dec i))))]
(when j
(let [vj (v j)
l (loop [i (dec len)]
(if (< vj (v i)) i (recur (dec i))))]
(loop [v (assoc v j (v l) l vj) k (inc j) l (dec len)]
(if (< k l)
(recur (assoc v k (v l) l (v k)) (inc k) (dec l))
v))))))
(defn- vec-lex-permutations [v]
(when v (cons v (lazy-seq (vec-lex-permutations (iter-perm v))))))
(defn lex-permutations
"Fast lexicographic permutation generator for a sequence of numbers" [c]
(lazy-seq (let [vec-sorted (vec (sort c))]
(if (zero? (count vec-sorted))
(list [])
(vec-lex-permutations vec-sorted)))))
(defn permutations
"All the permutations of items, lexicographic by index" [items]
(let [v (vec items)]
(map #(map v %) (lex-permutations (range (count v) )))))
This comes from the combinatorics library and I think it is instructive to walk through each function to see what is going on.
Permutations simply creates a new vector the size of the original vector. Then passes that off to lex-permutations which returns all the permutations of that new vector [1..N]. It then takes the original elements and maps those over the permutations to return the elements.
Lex-permutations in our case doesn’t do much. We already have a sorted vector so it just passes the vector to vec-lex-permutations.
Vec-lex-permutations starts with [1..N] and then builds a new vector [[1..N]..[N..1]] by repeatedly calling iter-perm. Iter-perm will return a permutations of [1..N] until it gets to [N..1] and then it will return a nil which will end the iteration.
Finally we come to the iter-perm function. This guys is where most of the work happens. I think it is instructive to walk through and example with [1 2] as the input to vec-lex-permutations and see what happens. Before we do that though on a high level this function takes in sequence [1..N] goes through permutations until it gets to [N..1] and then outputs nil after that. This nil is what signals the stop of vec-lex-permutations gives you the sequence of permutations [[1..N]..[N..1]].
So what happens with [1 2] well in iter-perm we have.
(defn- iter-perm [v] ; 1. v = [1 2]
(let [len (count v) ; 2. len = 2
j (loop [i (- len 2)] ; 3. j = 0 ; i = 0
(cond (= i -1) nil ; 4. i != -1
(< (v i) (v (inc i))) i ; 5. return i (0)
:else (recur (dec i))))] ; 6. skip
(when j ; 7. j = 0
(let [vj (v j) ; 8. vj = 1
l (loop [i (dec len)] ; 8. l = 1 ; i = 1
(if (< vj (v i)) i (recur (dec i))))] ; 10. 1 < 2 => i = 1
(loop [v (assoc v j (v l) l vj) k (inc j) l (dec len)] ; 11. v = [2 1] ; k = 1 ; l = 1
(if (< k l) ; 12. 1 < 1 != True
(recur (assoc v k (v l) l (v k)) (inc k) (dec l)) ; 13. skip
v)))))) ; 14. return v ([2 1])
The right hand steps show what happens, but basically on the first invocation we find the first permutation [1..N] is [1 2] and the second is [N..1] which is [2 1] and the next call will give us nil which stops the sequence and passes back up the stack [[1 2][2 1]] which is all the permutations of our two element vector.
This was definitely an interesting problem and I’m glad to see the clojure implementation.