# [racket] shortest paths, resource allocation/scheduling

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.
Ryan