Three hours ago, Ryan Culpepper wrote: > Here's the basic idea: > > ;; subsets-of-size : nat list -> (listof list) > (define (subsets-of-size n l) > (cond [(zero? n) (list null)] > [else > (for*/list ([ne-list (pair-fold-right cons null l)] > [subsetN-1 > (in-list (subsets-of-size (sub1 n) > (cdr ne-list)))]) > (cons (car ne-list) subsetN-1))])) > > This has bad complexity, I believe, although I haven't calculated > it. If you add in memoization, though, you should get good > (optimal?) complexity and optimal tail-sharing.
There was a long discussion about this on c.l.scheme a number of years ago, with a bunch of people trying to write optimized code. The bottom line was that a simpe memoization was as fast as the best hand-optimized versions. See the results here: http://scheme.barzilay.org/subsets/ with a link to the sources that I used. (But note that it's really ancient (around 10 years, I think), so the code looks bad, and the timings are likely to look different now.) -- ((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay: http://barzilay.org/ Maze is Life! _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
