# Is there a procedure for combinations of list elements?

**URL:** <https://racket.discourse.group/t/is-there-a-procedure-for-combinations-of-list-elements/3148>\
**Category:** Questions & Answers\
**Tags:** question\
**Created:** [September 3, 2024, 2:46pm UTC](https://racket.discourse.group/t/is-there-a-procedure-for-combinations-of-list-elements/3148 "2024-09-03T14:46:09Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![joskoot](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/joskoot/32/1964_2.png) [@joskoot](https://racket.discourse.group/u/joskoot)\
**Post date:** [September 3, 2024, 2:46pm UTC](https://racket.discourse.group/t/is-there-a-procedure-for-combinations-of-list-elements/3148/1 "2024-09-03T14:46:10Z")

</div>

Looking around I could not find a procedure that given a list lst and a natural number n returns a list of all (expt (length lst) n) combinations of the elements of the lst. I have concocted the following, but probably another and more efficient procedure is already available somewhere. Is there?

```scheme
#lang racket/base

#|====================================================================================================
Procedure : (combinations ‹lst› ‹n›) --> (listof list?)
‹lst› : list?
‹n› : natural?

Returns the list of all combinations of ‹n› elements of ‹lst›. Let ‹m› be the length of ‹lst›.
The result is a list of (expt ‹m› ‹n›) elements, each element being a list of ‹n› elements of ‹lst›,
not necessarily distinct elements. If ‹lst› is empty and ‹n› is zero, the result is (()), but if ‹lst›
is empty and ‹n› is not zero, the result is (). This ensures that always:

   (= (length (combinations ‹lst› ‹n›)) (expt (length ‹lst›) ‹n›))

====================================================================================================|#

; To be commented out

(define (examples)
  (define-syntax-rule (--> (combinations lst n) expected)
    (let ((computed (combinations lst n)))
      (unless
        (and
          (= (length computed) (expt (length lst) n))
          (equal? computed 'expected))
        (error 'test-combinations "wrong~n expr: ~s~n expected: ~s~n computed: ~s"
          'expr 'expected computed))))
  (-->
    (combinations '() 0)
    (()))
  (-->
    (combinations '() 10)
    ())
  (-->
    (combinations '(a) 0)
    (()))
  (-->
    (combinations '(a) 1)
    ((a)))
  (-->
    (combinations '(a) 2)
    ((a a)))
  (-->
    (combinations '(a b) 0)
    (()))
  (-->
    (combinations '(a b) 1)
    ((a) (b)))
  (-->
    (combinations '(a b) 2)
    ((a a) (a b) (b a) (b b)))
  (-->
    (combinations '(a b) 3)
    ((a a a) (a a b) (a b a) (a b b) (b a a) (b a b) (b b a) (b b b)))
  (-->
    (combinations '(a) 3)
    ((a a a)))
  (-->
    (combinations '(a a) 3)
    ((a a a) (a a a) (a a a) (a a a) (a a a) (a a a) (a a a) (a a a)))
  (-->
    (combinations '(a b c) 0)
    (()))
  (-->
    (combinations '(a b c) 1)
    ((a) (b) (c)))
  (-->
    (combinations '(a b c) 2)
    ((a a) (a b) (a c) (b a) (b b) (b c) (c a) (c b) (c c)))
  (-->
    (combinations '(a b c) 3)
    ((a a a) (a a b) (a a c) (a b a) (a b b) (a b c) (a c a) (a c b) (a c c)
     (b a a) (b a b) (b a c) (b b a) (b b b) (b b c) (b c a) (b c b) (b c c)
     (c a a) (c a b) (c a c) (c b a) (c b b) (c b c) (c c a) (c c b) (c c c))))

;=====================================================================================================

(require
  (only-in racket natural?)
  (only-in racket/contract contract-out -> listof))

(provide
  (contract-out
    (combinations (-> list? natural? (listof list?)))))

(define (combinations lst n)
  (cond
    ((zero? n) '(()))
    ((null? lst) '())
    (else
      (define (combinations n)
        (cond
          ((= n 1) (map list lst))
          (else
            (define sub-combinations (combinations (sub1 n)))
            (apply append
              (for/list ((conser in-consers))
                (map conser sub-combinations))))))
      (define consers (for/list ((e (in-list lst))) (λ (combi) (cons e combi))))
      (define in-consers (in-list consers))
      (combinations n))))

;=====================================================================================================

; To be commented out:

(examples)

```

---

<div class="post-metadata">

**Author:** ![shawnw](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/shawnw/32/1031_2.png) [@shawnw](https://racket.discourse.group/u/shawnw)\
**Post date:** [September 3, 2024, 5:11pm UTC](https://racket.discourse.group/t/is-there-a-procedure-for-combinations-of-list-elements/3148/2 "2024-09-03T17:11:22Z")

</div>

There's already a function named [`combinations` in `racket/list`](https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28lib._racket%2Flist..rkt%29._combinations%29%29); I'd use a different name.

My quick and dirty version using [`cartesian-product`](https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28lib._racket%2Flist..rkt%29._cartesian-product%29%29):

```scheme
(require racket/list)
(define (all-combinations list n)
  (apply cartesian-product (make-list n list)))

```

---

<div class="post-metadata">

**Author:** ![joskoot](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/joskoot/32/1964_2.png) [@joskoot](https://racket.discourse.group/u/joskoot)\
**Post date:** [September 3, 2024, 6:30pm UTC](https://racket.discourse.group/t/is-there-a-procedure-for-combinations-of-list-elements/3148/3 "2024-09-03T18:30:18Z")

</div>

Thanks.  
Procedure combinations does not what I want, but your quick and clean procedure all-combinations using procedure cartesian-product does it well.  
Thanks again.

---

<div class="post-metadata">

**Author:** ![joskoot](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/joskoot/32/1964_2.png) [@joskoot](https://racket.discourse.group/u/joskoot)\
**Post date:** [September 4, 2024, 4:23pm UTC](https://racket.discourse.group/t/is-there-a-procedure-for-combinations-of-list-elements/3148/4 "2024-09-04T16:23:52Z")

</div>

Simpler version of my combinations. Somewhat faster than my previous version and (cartesian-product (make-list n lst)).

```scheme
(define (combinations lst n)
  (cond
    ((= n 0) '(()))
    ((null? lst) '())
    (else
      (define in-lst (in-list lst))
      (define (combinations n)
        (cond
          ((zero? n) (map list lst))
          (else
            (define in-combis (in-list (combinations (sub1 n))))
            (for*/list ((e in-lst) (combi in-combis)) (cons e combi)))))
      (combinations (sub1 n)))))

```