99 Clojure Problems – 26: Generate the Combinations of K Distinct Objects Chosen From the N Elements of a List

"In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficients). For pure mathematicians, this result may be great. But we want to really generate all the possibilities."

Example:

(deftest p26-combinations
  (is (= '((0 1) (0 2) (1 2)) (combinations 2 (range 3))))
  (is (= 220 (count (combinations 3 (range 12))))))

Solution:

Here is my thinking, which is inspired by SICPs counting change example: If you want to enumerate all combinations of 2 distinct objects chosen from the list (0 1 2) you could fix the first element to be the first element of the list. That leaves you with a list of two elements and one more object to choose. There are only two combinations for C(2, 1): the two remaining elements of the list. Join them to the first elements we have already chosen and we end up with (0 1) and (0 2). Do the same thing again: Enumerate all combinations of two distinct objects from the remaining list (1 2), there is just one: the list itself is the answer.

We can generalize these observations into a solution: combinations of k distinct objects chosen from a list of n elements are the first element of the list conjoined to the combinations of k-1 distinct objects from the rest of the list, plus all combinations of k distinct objects from the list without its first element (again: the rest or tail of the list).

Read more about this series.