Tail recursive Clojure function for computing combinations

Question

I have a function that, given a vector, returns all unordered combinations:

(defn combination [ps]
  (loop [acc []
         ps ps]
    (if (= 2 (count ps))
      (conj acc (apply vector ps))
      (recur (apply conj acc (map #(vector (first ps) %) (rest ps)))
             (rest ps)))))

This works just fine, but seems a bit convoluted to me.

Is there a more straight-forward, idiomatic way to accomplish this in Clojure? I'm happy to use a Clojure core or library function, as this is certainly part of my definition of "idiomatic". :)

Answer 1

Your code returns all selections of two elements taken in order. Another way to do this is ...

(defn combination [s]
  (let [tails (take-while next (iterate rest s))]
    (mapcat (fn [[f & rs]] (map #(vector f %) rs)) tails)))

This is shorter than yours and is lazy too. But it's likely to be slower.

Answer 2

Clojure has clojure.math.combinatorics which contains many convenient functions. So arguably the "idiomatic" way to do what you did in Clojure would be to import/require clojure.math.combinatorics and then simply call combinations with n = 2.

...>  (comb/combinations [1 2 3 4] 2)
((1 2) (1 3) (1 4) (2 3) (2 4) (3 4))

For this to work you'll need to first add the correct dependency.

As I write this the latest version is: [org.clojure/math.combinatorics "0.0.7"]

I did then require it ":as comb":

(:require [clojure.math.combinatorics :as comb]

In case you don't want to use math.combinatorics, you can edit your question to precise it and I'll delete my answer.

Answer 3

Somewhat facetiously ...

(defn combination [ps]
  (clojure.math.combinatorics/combinations ps 2))

... which is lazy, but the source code is two or three times as long as yours.