[racket] shortest paths, resource allocation/scheduling

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-bounces at racket-lang.org [mailto:users-bounces at racket-lang.org]
On Behalf Of Eli Barzilay
Sent: lunes, 05 de diciembre de 2011 21:17
To: Ryan Culpepper
Cc: users at 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