Problem Statement

The set of combinations with repetitions is computed from a set,

S

{\displaystyle S}

(of cardinality

n

{\displaystyle n}

), and a size of resulting selection,

k

{\displaystyle k}

, by reporting the sets of cardinality

k

{\displaystyle k}

where each member of those sets is chosen from

S

{\displaystyle S}

. In the real world, it is about choosing sets where there is a “large” supply of each type of element and where the order of choice does not matter. For example: Note that both the order of items within a pair, and the order of the pairs given in the answer is not significant; the pairs represent multisets. Also note that doughnut can also be spelled donut.

Let's start with the solution:

#lang racket
(define (combinations xs k)
  (cond [(= k 0)     '(())]
        [(empty? xs) '()]
        [(append (combinations (rest xs) k)
                 (map (λ(x) (cons (first xs) x))
                      (combinations xs (- k 1))))]))