[racket] shortest paths, resource allocation/scheduling

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