Hi, I wrote a function doing the following:
it takes a list and an integer as arguments and returns a list of lists
which are all different subsets of length n from the given list:

(subset '(1 2 3 4) 2)
--> ((1 2) (1 3) (1 4) (2 3) ( 2 4) (3 4))

I would like to have your comments: can I improve the function
(that I use very much; all advice to have quicker or anything better
will be fine).
[The sublists are not given in a "pretty" order, because I don't need it;
since I take them are subsets (and not lists), (4 2) is for me the
same as (2 4)]

(define (subsets l n)
  (let ((subsets* '()))
    (letrec ((subsets0 (lambda (l2 l* n2)
                (if (zero? n2) (set! subsets* (cons l* subsets*))
                  (do ((i 0 (+ i 1)))
                      ((> i (- (length l2) n2)) subsets*)
                    (subsets0 (list-tail l2 (+ i 1))
                            (cons (list-ref l2 i) l*) (- n2 1)))))))
      (subsets0 l '() n))))

subset '() n ==> '() : there are no subsets in an empty set
subset l 0   ==> '(()): the only subset of size (cardinality 0) is an
                  empty set

subset (a . tail) n ==> { (a . x) | x <- subset tail (n-1) } Union
                        subset tail n
that is, subsets of size n will either contain the element a, or will
not contain it.

This mathematical definition directly translates to Scheme.

(define (subset l n)
  (cond
   ((<= n 0) '(()))
   ((null? l) '())
   ((= n 1) (map list l))
   (else
    (append
     (let ((hd (car l)))
       (map
        (lambda (lst) (cons hd lst))
        (subset (cdr l) (- n 1))))
     (subset (cdr l) n)))))

The solution is purely functional.

Note, the code has an optimization for the case n=1, in which case the
answer is a set of all singleton subsets.

Example:

(display (subset '(1 2 3 4) 0))
===> (())

(display (subset '(1 2 3 4) 1))
===> ((1) (2) (3) (4))

(display (subset '(1 2 3 4) 2))
===> ((1 2) (1 3) (1 4) (2 3) (2 4) (3 4))

(display (subset '(1 2 3 4) 3))
===> ((1 2 3) (1 2 4) (1 3 4) (2 3 4))

(display (subset '(1 2 3 4) 4))
===> ((1 2 3 4))

(display (subset '(1 2 3 4) 5))
===> ()

(define l '(a b c d e f g))

And you want the subsets of size 3.  First, you'll calculate all the subsets
which start with 'a, defined as 'a prepended onto the subsets of size 2
starting after 'a.  The first subset of size 2 you generate will start with
'b, and when you've generated all those, you'll generate those that start at
'c, and so on.

When you're done generating the subsets that start with 'a, you'll generate
the subsets of size 3 that start with 'b, and then (once again) you'll
generate the subsets of size 2 that start with 'c.  In fact, all the subsets
you generate as the recursive step of creating sets of size 3 starting with 'b
will have already been generated, as part of the recursive step for 'a.  That
causes your time-complexity to skyrocket as n gets larger.

   Sometime when I've had a little more sleep and a little less coffee I'll
try to put together a solution.  But the problem is similar to the simple (but
highly wasteful) definition of the Fibonacci series:

(define (fibs n)
   (cond ((eq? n 0) 0)
         ((eq? n 1) 1)
         (else (+ (fibs (- n 1)) (fibs (- n 2))))))

Any (fibs x) where x is between 0 and n may be calculated many, many times,
when it needn't be calculated more than once.  Likewise, there's no need to
calculate the list of sets of size n from l including l's first element more
than once.

(define (combos l n)
  (letrec ((subsets0 (lambda (l2 l* n2 acc)
                       (if (zero? n2)
                           (cons l* acc)
                           (do ((rest l2 (cdr rest))
                                (available (length l2) (- available 1))
                                (acc acc (subsets0 (cdr rest)
                                                   (cons (car rest) l*)
                                                   (- n2 1)
                                                   acc)))
                               ((< available n2) acc))))))
    (subsets0 l '() n '()))))

        Using Chez Scheme 6.1 under Linux on a 700MHz Pentium III, COMBOS
took 250 ms of cpu time to find all the ten-element subsets of a
twenty-element set; SUBSETS took 460 ms.

   Anyway, my implementation, "subs" uses up a lot of heap space compared to,
say, "combos" posted by John Stone, and incurs more garbage collection, but
still comes out faster:

(define (expand xs sets)
    (if (or (null? xs) (null? sets))
        ()
        (cons
            (apply append (map (lambda (set) (map (lambda (s) (cons (car xs)
s)) set)) (cdr sets)))
            (expand (cdr xs) (cdr sets)))
))

(define (subs xs n)
    (cond ((eq? 0 n) ())
        (else
            (do ((i 1 (+ i 1))
                 (acc (map (lambda (x) (list (list x))) xs) (expand xs acc)))
                ((= i n) (apply append acc))))))

   Sorry if I spread a bunch of misinformation with that tree-recursion
comparison: I'm still not sure why I'm wrong, but I had the same problem with
the Monty Hall thing.

  ;; Returns all n-length subsets of the list l.
  (define (subsets l n)
    ;; ss prepends each n-length subset of l to little-acc, and returns
    ;; a list of the resulting sets, prepended to big-acc.  len must be
    ;; the length of l.
    (let ss ((l l) (len (length l)) (n n) (little-acc '()) (big-acc '()))
      (cond ((zero? n) (cons little-acc big-acc))
            ((< len n) big-acc)
            (else (ss (cdr l) (- len 1) (- n 1) (cons (car l) little-acc)
                      (ss (cdr l) (- len 1) n little-acc big-acc))))))

Is that faster or slower on your system?

   On my interpreter (SCM), subs and subs2 take less time, but use around 4
times as many storage cells for intermediate values.  It's a tradeoff that's
advantageous on some interpreters, I guess.

   Is Chez Scheme in Debian?

   Listing for subs2 follows:

(define (subs-base xs)
  (if (null? xs)
      ()
      (let* ((rest (subs-base (cdr xs)))
             (first (if (null? rest) () (car rest))))
        (cons (cons (list (car xs)) first) rest)
)))

(define (subs-expand xs sets)
  (if (or (null? xs) (null? sets) (null? (cdr sets)))
      ()
      (let* ((rest (subs-expand (cdr xs) (cdr sets)))
             (first (if (null? rest) () (car rest))))
        (cons
         (append (map (lambda (x) (cons (car xs) x)) (cadr sets)) first)
         rest
))))

(define (subs2 xs n)
  (if (eq? 0 n)
      ()
      (do ((i 1 (+ i 1))
           (acc (subs-base xs) (subs-expand xs acc)))
          ((eqv? i n) (car acc)))
))

So, you must have tried his code too, getting to a conclusion that it
is useless if you care about speed...  I tried it too (s1=subsets,
s2=subs, s3=subs2, s4=combos, s5=subset):

| > (define a '(a b c d e f g h i j k l m n o p q r s t u v w x y z))
| > (time (begin (s1 a 8) #f))
| cpu time: 25520 real time: 25485 gc time: 7580
| > (time (begin (s2 a 8) #f))
| cpu time: 10730 real time: 10715 gc time: 5640
| > (time (begin (s3 a 8) #f))
| cpu time: 7290 real time: 7245 gc time: 2610
| > (time (begin (s4 a 8) #f))
| cpu time: 13720