[racket] shortest paths, resource allocation/scheduling

On Mon, 2011-12-05 at 09:00 -0700, Ryan Culpepper wrote:
> On 12/05/2011 08:40 AM, Sam Tobin-Hochstadt wrote:
> > On Mon, Dec 5, 2011 at 10:00 AM, Geoffrey S. Knauth<geoff at knauth.org>  wrote:
> >> I'm wondering if there is something in the now very rich set of Racket libraries that already does this.  Let's say I have 5 points {A,B,C,D,E}.  I want to interconnect all of them:
> >>
> >> {AB,AC,AD,AE,AF,BC,BD,BE,BF,CD,CE,CF,DE,DF,EF}
> >>
> >> That's 15 edges rather than the 5x5=25 that a dumb interconnect
> >> would do.  To start, I just need to track and sort the edge
> >> weights, and AB is the same as BA.
> >
> > Here's the start of an answer (sadly quadratic, but for N=121 I don't
> > think that will matter much):
> >
> > #lang racket
> > (require unstable/sequence)
> > (define (subsets-of-size-2 l)
> >    (for*/lists (r) ([i l] [j l]
> >                     #:unless (eq? i j)
> >                     #:unless (member (cons j i) r))
> >      (cons i j)))
> >
> > (for ([(p q) (in-pairs (subsets-of-size-2 '(A B C D E F)))])
> >    (printf "~a<->  ~a\n" p q))
> >
> 
> That looks quartic in the length of l, because of the member check.
> 
> Here's a quadratic version:
> 
> (require srfi/1)
> (define (subsets-of-size-2 l)
>    (for*/list ([ne-sublist (pair-fold-right cons null l)]
>                [b (in-list (cdr ne-sublist))])
>      (cons (car ne-sublist) b)))
> 
> Note: (pair-fold-right cons null l) produces a list of the non-empty 
> sublists of l.

Hi Ryan,
some time ago I was looking for an efficient algorithm in Racket to
extract k-sized combinations of elements from a list l... Could you
provide a generalisation of your code, I mean "subset-of-size-k" 
where k < (lenght l) ?
TIA,
Maurizio.

> Ryan
> _________________________________________________
>   For list-related administrative tasks:
>   http://lists.racket-lang.org/listinfo/users