Let’s build a function to generate all combinations of a set.

As an example, let’s pretend our set S is #{a, b, c, d} and we want all combinations of size n=3. That would look like:

#{a, b, c}

#{a, b, d}

#{a, c, d}

#{b, c, d}

All combinations of size 2 from S would look like:

#{a, b}

#{a, c}

#{a, d}

#{b, c}

#{b, d}

#{c, d}

In English, the combinations (of size n) of a set S are all unique subsets of size n of S.

A pretty simple concept, yet can be aggravatingly difficult to implement.

There are many possible approaches, such as hacking away at array index arithmetic and the like.

We want to try to take a more conceptually natural approach.

The main insight is that combinations have a recursive structure. If I know the combinations of size n, it is fairly straightforward to generate the combinations of size n+1.

This is illustrated in the following graphic:

We start at the top with a single vector consisting of two elements: the combinations of size n and the remaining elements of the set S we are generating from. To generate the n+1 combinations from the n combinations, we call the expand function on every vector at size n. The expand function takes the single two-element vector and returns all the possible child combinations as visualized in the graphic. We iterate this process to build higher order combinations.

This logic is captured in the following code:

(defn combos

  [n s]        

  (if (zero? n)

    (list [[] s])

    (mapcat

      expand

      (combos (dec n) s))))

Where the expand function is given by:

(defn expand

  [[a b]]

  (when-not

    (empty? b)

    (cons

      [(conj a (first b))

       (rest b)]

      (expand [a (rest b)]))))

Trying it out:

=> (map first (combos 3 '(1 2 3 4)))

([1 2 3] [1 2 4] [1 3 4] [2 3 4])

Happy combinating!