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?