[racket] shortest paths, resource allocation/scheduling

From: Veer (diggerrrrr at gmail.com)
Date: Mon Dec 5 11:05:34 EST 2011

I am not too sure if this is less than quadratic ??

(define points (list->vector '(a b c d e f)))
(define l (vector-length points))

(define (gen org start end)
  (for/list ([n (in-range start end )])
    (cons (vector-ref points org ) (vector-ref points n ))))

(for/fold ([accum empty]) ([i (in-range l)])
  (append accum (gen i (+ i 1) l)))


On Mon, Dec 5, 2011 at 9:10 PM, Sam Tobin-Hochstadt <samth at ccs.neu.edu> 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))
>
> --
> sam th
> samth at ccs.neu.edu
>
> _________________________________________________
>  For list-related administrative tasks:
>  http://lists.racket-lang.org/listinfo/users



Posted on the users mailing list.