|
|
comp.lang.scheme |
> (subset '(1 2 3 4) 2) > I would like to have your comments: can I improve the function (define (combos l n) Using Chez Scheme 6.1 under Linux on a 700MHz Pentium III, COMBOS -- baruc...@libertysurf.france (Thomas Baruchel) writes: Here's a version that appears to be faster. It uses an accumulator
> 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:
> --> ((1 2) (1 3) (1 4) (2 3) ( 2 4) (3 4))
> (that I use very much; all advice to have quicker or anything better
> will be fine).
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.
(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 '()))))
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/