Is there a procedure for combinations of list elements?

Questions & Answers
1

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?

#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)
2

There's already a function named combinations in racket/list; I'd use a different name.

My quick and dirty version using cartesian-product:

(require racket/list)
(define (all-combinations list n)
  (apply cartesian-product (make-list n list)))
1 Like
3

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.

4

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

(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)))))
1 Like