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
                 (lambda (head)
                   (map
                    (lambda (tail) (cons head tail))
                    (permutations (remove head l))))
                 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 [head]
                      (map (fn [tail]
                             (cons head tail))
                           (permutations (remove #{head} l))))
                    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)
    (for [head s
          tail (permutations (remove #{head} s))]
      (cons head tail))))

(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)
     (for [head s
           tail (permutations (remove #{head} s))]
       (cons head tail)))))

(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)
     (for [head s
           tail (permutations (remove #{head} s))]
       (cons head tail))
     [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)
     (for [head s
           tail (permutations (remove-first #{head} s))]
       (cons head tail))
     [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)
     (for [head s
           tail (permutations (disj s head))]
       (cons head tail))
     [s])))

(permutations #{1 2 3})
=> ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))

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.

A more comprehensive collection of functions for generating permutations and combinations can be found in the clojure.math.combinatorics library.