Simple combinatorics in Clojure

I've recently encountered this seemingly straightforward problem in a coding kata Best Travel, which requires finding all combinations of n elements in a list. It turned out that I still have some ways to go to think in functional way.

Problem statement

For a given list lst, find all possible combinations of size n, so that each element in the resultant list comes from the original list, but do not repeat. Also, the order of elements in resultant list does not matter.

So, as a simple example: given list (1 2 3), and size of 2, the output should be ((1 2) (1 3) (2 3)).

As an example with duplicate elements in original list: given list (1 1 2 3), and size of 3, the output should be ((1 1 2) (1 1 3) (1 2 3) (1 2 3)).

First Attempt

The immediate solution that came to me was list comprehension. As I was practicing Clojure, I thought of for function. Also, I had a faling test, which asserts 3 elements, so I wrote a solution for 3 first.

(defn for-comb [coll]
  (let [possibilities (for [x coll
                            y coll
                            z coll
                            :while (and (not= x y) (not= y z))]
                        (list x y z))]
    (->> possibilities
         (map sort)
         (distinct))))

(for-comb '(1 1 2 3))
;; ((1 1 2) (1 1 3) (1 2 3) (2 2 3))

Ok, this works, then I moved on to generalize for n elements. Hmmm how would I do that? What should be in the for binding?

Second Attempt

The for approach seemed quite difficult to be generalized. (Or maybe I'm not aware of a good solution using for yet.) Next best thing, is to use index.

(defn vec-remove
  [pos coll]
  (into (subvec coll 0 pos) (subvec coll (inc pos))))

(defn index-comb [coll n]
  (for [i (range n)]
    ;; what do I do now)
  ))

At this point, it already points to using recursion. I would need to get one element out of the list, then recurse to get the next element from the rest of the list.

Third Attempt

In 2023, the easiest way for me to continue would be to ask ChatGPT. So here is the solution it gave me:

(defn combinations [coll size]
  (cond
    (= size 0) '(())
    (empty? coll) '()
    :else (concat (map (fn [x] (cons (first coll) x))
                       (combinations (rest coll) (dec size)))
                  (combinations (rest coll) size))))

(combinations [1 1 2 3] 3)
;; ((1 1 2) (1 1 3) (1 2 3) (1 2 3))

Brilliant, so let's see how it works.

It does this by recursively generating combinations from the rest of the list, both with and without the first item, and concatenates these.

The base cases are when size is 0 (return a list with an empty list) and when the collection is empty (return an empty list).

So, for the example (1 2 2 3), it contains two possible sets of solutions. First, solutions containing the first 1. Second, solutions that do not contain 1. To find the first set, it takes the 1, and rest of the list (2 2 3), then try to find 2 element combinations of (2 2 3) and append 1 to each combination. To find the second set, it just repeats the process of the same function but with one element fewer. Eventually, both solutions converge onto the base case.

clojure.math.combinatorics solution

There is also an official combinatorics library that already solves this problem. You can find the actual library solution here

Final words

After looking at my original thought process and the recursion solution, the recursion makes perfect sense!