[plt-scheme] Combinations

======= At 2005-06-03, 15:29:50 Iain Gray wrote: =======
>
>Does anyone know of an efficient way of generating the combinations of 
>k  objects from n objects? I could generate permutations and then 
>filter out on set equality, but my example is largish in choosing 4 
>from 70.
>
>Any advice would be appreciated.
>
>Iain
>

Give these n objects an order, and then when "generate permutations",
only allow "smaller" objects be placed befor "bigger" ones.

(define (combinations k nlst)
  (cond ((zero? k)
         '(()))
        ((null? nlst)
         '())
        (else
         (append (map (lambda (k-1)
                        (cons (car nlst) k-1))
                      (combinations (- k 1) (cdr nlst)))
                 (combinations k (cdr nlst))))))

> (combinations 4 '(1 2 3 4 5 6 7 8))
((1 2 3 4)
 (1 2 3 5)
 (1 2 3 6)
 (1 2 3 7)
 (1 2 3 8)
 (1 2 4 5)
 (1 2 4 6)
 (1 2 4 7)
 (1 2 4 8)
 (1 2 5 6)
 (1 2 5 7)
 (1 2 5 8)
 (1 2 6 7)
 (1 2 6 8)
 (1 2 7 8)
 (1 3 4 5)
 (1 3 4 6)
 (1 3 4 7)
 (1 3 4 8)
 (1 3 5 6)
 (1 3 5 7)
 (1 3 5 8)
 (1 3 6 7)
 (1 3 6 8)
 (1 3 7 8)
 (1 4 5 6)
 (1 4 5 7)
 (1 4 5 8)
 (1 4 6 7)
 (1 4 6 8)
 (1 4 7 8)
 (1 5 6 7)
 (1 5 6 8)
 (1 5 7 8)
 (1 6 7 8)
 (2 3 4 5)
 (2 3 4 6)
 (2 3 4 7)
 (2 3 4 8)
 (2 3 5 6)
 (2 3 5 7)
 (2 3 5 8)
 (2 3 6 7)
 (2 3 6 8)
 (2 3 7 8)
 (2 4 5 6)
 (2 4 5 7)
 (2 4 5 8)
 (2 4 6 7)
 (2 4 6 8)
 (2 4 7 8)
 (2 5 6 7)
 (2 5 6 8)
 (2 5 7 8)
 (2 6 7 8)
 (3 4 5 6)
 (3 4 5 7)
 (3 4 5 8)
 (3 4 6 7)
 (3 4 6 8)
 (3 4 7 8)
 (3 5 6 7)
 (3 5 6 8)
 (3 5 7 8)
 (3 6 7 8)
 (4 5 6 7)
 (4 5 6 8)
 (4 5 7 8)
 (4 6 7 8)
 (5 6 7 8))
-
Chongkai Zhu
The right idea was actually had very early, but somehow didn't win for a long time.