If there is a less-than predicate for the elements of the list, the list can be sorted and things may be speeded up, I think. Jos
-----Original Message----- From: users-boun...@racket-lang.org [mailto:users-boun...@racket-lang.org] On Behalf Of Eli Barzilay Sent: lunes, 05 de diciembre de 2011 21:17 To: Ryan Culpepper Cc: users@racket-lang.org Subject: Re: [racket] shortest paths, resource allocation/scheduling 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 _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
