[racket] shortest paths, resource allocation/scheduling

On 12/05/2011 09:20 AM, Maurizio Giordano GMAIL wrote:
> 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) ?

Here's the basic idea:

;; subsets-of-size : nat list -> (listof list)
(define (subsets-of-size n l)
   (cond [(zero? n) (list null)]
         [else
          (for*/list ([ne-list (pair-fold-right cons null l)]
                      [subsetN-1
                       (in-list (subsets-of-size (sub1 n)
                                                 (cdr ne-list)))])
            (cons (car ne-list) subsetN-1))]))

This has bad complexity, I believe, although I haven't calculated it. If 
you add in memoization, though, you should get good (optimal?) 
complexity and optimal tail-sharing.

Ryan