Generate all permutations in Clojure

Question

Given a set, generate all permutations:

(permutations #{1 4 5}) => ((5 4 1) (4 5 1) (5 1 4) (1 5 4) (4 1 5) (1 4 5))

Here's what I cobbled together:

(defn perm-r [allPerms currentPerm input i]
 (cond
 (empty? input) (conj allPerms currentPerm)
 (< i 0) allPerms
 :else (perm-r
 (perm-r
 allPerms
 (conj currentPerm (nth input i))
 (remove (fn [x] (= x (nth input i))) input)
 (dec
 (count
 (remove
 (fn [x] (= x (nth input i)))
 input))))
 currentPerm
 input
 (dec i))))
(defn permutations [a-set]
 (perm-r `() `() (seq a-set) (dec (count a-set))))

I thought my solution was awful, so I went to look for other solutions and found this:

(defn rotations [a-seq]
 (distinct (map concat (tails a-seq) (inits a-seq))))
(defn permutations [a-set]
 (if (empty? a-set)
 (list ())
 (apply concat (map (fn [x] (map cons (repeat (first x))
 (permutations (rest x))))
 (rotations a-set)))))

It looks so elegant! I'm not used to functional programming, so I find the execution flow immensely difficult to follow. In particular, I don't understand what's being concatenated. Is the result of the first map call (which represents what exactly?) to every rotation of a-set?

Any tips on improving my thought process so that I could come up with a solution like that on my own? I'm used to programming imperatively and I don't find functions like map or apply intuitive. Is there a way to make this function more readable or improve it further in other ways?

• Alan Thompson: There are many ways of doing it. If you would like to see a very effective implementation, please look at the source for github.com/clojure/math.combinatorics

Answer 1

Let's clean the code up a bit.

Function tails gives us all the possible ending sub-sequences. For example ...

(tails (range 3)) ; ((0 1 2) (1 2) (2) ())

And inits gives us all the initial sub-sequences. For example ...

(inits (range 3)) ; (() (0) (0 1) (0 1 2))

To get the rotations, we marry the init with the corresponding tail,using concat. If we just

(defn rotations [a-seq]
 (map concat (tails a-seq) (inits a-seq)))

` ... then we get the original sequence at both ends:

(rotations (range 5)) ; ((0 1 2 3 4) (1 2 3 4 0) (2 3 4 0 1) (3 4 0 1 2) (4 0 1 2 3) (0 1 2 3 4))

The given code uses distinct to get rid of the duplicate. It's faster and simpler to use rest:

(defn rotations [a-seq]
 (rest (map concat (tails a-seq) (inits a-seq))))

Now

(rotations (range 5)) ; ((1 2 3 4 0) (2 3 4 0 1) (3 4 0 1 2) (4 0 1 2 3) (0 1 2 3 4))

And we're ready to generate all the permutations. We can rewrite the given code as follows:

(defn permutations [a-set]
 (if (empty? a-set)
 (list ())
 (mapcat
 (fn [[x & xs]] (map #(cons x %) (permutations xs)))
 (rotations a-set))))

• (mapcat f coll)is an abbreviation for (apply concat (map f coll)).
• (fn [[x & xs]] ... ) is a destructuring form that sets x to the first and xs to the rest of its sequence argument.
• #(cons x %) is an abbreviation for (fn [y] (cons x y)), a function that puts x on the front of its sequence argument.

For every rotation of the given set, the permutations function glues its first element onto each permutation of the rest of the elements, and then concatenates all these collections together. For example ...

(permutations (range 3))
; ((1 0 2) (1 2 0) (2 1 0) (2 0 1) (0 2 1) (0 1 2))

That's it.

---

The given inits ...

(defn inits [a-seq]
 (reverse (map reverse (tails (reverse a-seq)))))

... is somewhat overworked, on account of all the reverses. A neater way to get the rotations is

(defn rotations [a-seq]
 (let [a-vec (vec a-seq)]
 (for [i (range (count a-vec))]
 (concat (subvec a-vec i) (subvec a-vec 0 i)))))

• Petrus Theron: Where is tails defined?
• chbrown: I too figured tails would be in clojure.core, but it's simple enough to do (defn tails [coll] (take-while seq (iterate rest coll)))
• Simon Polak: Also inits could be written as (defn inits [coll] (reductions conj [] coll))