# Clojure: permutations

I was solving an Advent of Code problem and part of the solution required generating all the permutations of a set of numbers. Permutation is the act of arranging the members of a set into different orders. I wanted to write a recursive solution rather than an imperative solution. After some searching I found a Scheme implementation. As Scheme and Clojure are both dialects of Lisp, translating one into the other wasn't too difficult.

The Scheme implementation:

``````(define (permutations l)
(cond
((= (length l) 1) (list l))
(else (apply append
(map
(map
l)))))

(permutations '(1 2 3))
=> ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))
``````

A first pass at the translation sees some minor changes: `length` to `count`, `lambda` to `fn`, `append` to `concat` and finally `remove` in Clojure takes a predicate rather than an element to remove. This gives us:

``````(defn permutations [l]
(cond (= (count l) 1)
(list l)
:else
(apply concat
(map (fn [tail]
l))))

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

In Clojure, a nested `map` can be replaced with a `for` comprehension; with the first binding acting as the outer loop and the second binding as the inner loop. `l` has been renamed to `s` as the fundamental data structure in Clojure is the sequence and not the list:

``````(defn permutations [s]
(if (= (count s) 1)
(list s)

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

This recursive solution can be made to use a single stack frame by wrapping it in a `lazy-seq`:

``````(defn permutations [s]
(lazy-seq
(if (= (count s) 1)
(list s)

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

`count` is replaced with `next` to make the solution more idiomatic:

``````(defn permutations [s]
(lazy-seq
(if (next s)
[s])))

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

The permutation function is working fine. However, when duplicate values are passed, there are unexpected results:

``````(permutations '(2 2))
=> ((2) (2))
``````

In this case the output is `((2) (2))`, but the expected output should be `((2 2) (2 2))`, as each `2` is a separate item despite having the same value. This can be fixed by replacing `remove` with `remove-first`. This function removes the first element that matches the predicate rather than all elements that match it:

``````(defn remove-first [pred s]
(lazy-seq
(when-let [[x & xs] (seq s)]
(cond (pred x) xs
:else   (cons x (remove-first pred xs))))))

(defn permutations [s]
(lazy-seq
(if (next s)
[s])))

(permutations [2 2])
=> ((2 2) (2 2))
``````

This works as intended assuming it is desirable for the function to handle duplicate values. If this is not the case, this can be made explicit by passing in a set and using `disj` instead of `remove`:

``````(defn permutations [s]
(lazy-seq
(if (next s)
This implementation also has a performance advantage over the previous version with `remove`. This is because `disj` has `O(log32N)` (almost `O(1)`) performance compared to `remove` which has `O(N)` performance.