Subsets of a list - comp.lang.scheme

Message from discussion Subsets of a list

John David Stone

View profile

More options Jan 10 2002, 1:16 pm

Newsgroups: comp.lang.scheme

From: John David Stone <st...@cs.grinnell.edu>

Date: 10 Jan 2002 12:16:07 -0600

Local: Thurs, Jan 10 2002 1:16 pm

Subject: Re: Subsets of a list

  Reply to author
  |
  Forward
  | Print
  | View thread
  | Show original
  | Report this message
  | Find messages by this author
  

baruc...@libertysurf.france (Thomas Baruchel) writes:
> 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).

Here's a version that appears to be faster. It uses an accumulator
instead of a non-local variable and uses recursion over the list l2 rather
than over positions in that list, thus avoiding all of the calls to
LIST-REF and LIST-TAIL.

(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.

--
John David Stone - Lecturer in Computer Science and Philosophy
Manager of the Mathematics Local-Area Network
Grinnell College - Grinnell, Iowa 50112 - USA
st...@cs.grinnell.edu - http://www.cs.grinnell.edu/~stone/

Reply to author Forward