[racket] shortest paths, resource allocation/scheduling

On Dec 5, 2011, at 10:00 AM, Geoffrey S. Knauth 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.

I presume you mean 6 points {A,B,C,D,E,F}, and 15 edges rather than the 6x6=36 that a dumb interconnect would do.

As it happens, I ran into a similar problem in helping a student last week.  He's working in Java, so he's probably out of luck :-)  Anyway, I had pointed out to him the Java "for-each" loop, he got the idea, and he wanted to loop over all the distinct 2-element subsets of a given list.  He had two nested for-loops with integer indices, and wanted to know if there was a slicker way.  We concluded that Java for-each-loops by themselves don't do the job, but one could write a subsetsOfSize function and then say

for (Pair p : myList.subsetsOfSize(2)) { ... }

or in Racket
(for (p (subsets-of-size myList 2)) ...)

Of course, many scripting languages would allow you to extract the elements of p at the same time, e.g. Ruby
myList.subsetsOfSize(2).each { |x,y| ...}

which would take a bit of macro-wrangling in Racket.


Stephen Bloch
sbloch at adelphi.edu