Programming Praxis

This isn’t hard. We split the list, then apply the previous algorithm on the first half, then apply the previous algorithm on the second half. It does get messy because we put the whole thing in one big function:

(define (subset-sum-mitm xs t)
  (let-values (((f) (make-hash identity = #f 997))
               ((b) (make-hash identity = #f 997))
               ((front back) (split xs)))
    (let loop1 ((front front))
      (if (pair? front)
          (let loop2 ((ys (cons (cons 0 (list)) (f 'enlist))))
            (cond ((null? ys) (loop1 (cdr front)))
                  ((= (+ (car front) (caar ys)) t)
                    (cons (car front) (cdar ys)))
                  (else (f 'insert (+ (car front) (caar ys))
                                   (cons (car front) (cdar ys)))
                        (loop2 (cdr ys)))))
          (let loop3 ((back back))
            (if (null? back) #f
              (let loop4 ((ys (cons (cons 0 (list)) (b 'enlist))))
                (cond ((null? ys) (loop3 (cdr back)))
                      ((f 'lookup (- t (car back) (caar ys))) =>
                        (lambda (x)
                          (append (list (car back))
                                  (cdar ys) x)))
                      (else (b 'insert (+ (car back) (caar ys))
                                       (cons (car back) (cdar ys)))
                            (loop4 (cdr ys)))))))))))

Here’s an example that shows the time improvement in the two algorithms:

> (define ys '(267 439 869 961 1000 1153 1246 1598 1766 1922))
> (time (subset-sum ys 5842))
(time (subset-sum ys ...))
    2 collections
    125 ms elapsed cpu time, including 16 ms collecting
    0 ms elapsed real time, including 0 ms collecting
    7706816 bytes allocated, including 8325712 bytes reclaimed
(1766 1246 1000 961 869)
> (time (subset-sum-mitm ys 5842))
(time (subset-sum-mitm ys ...))
    no collections
    0 ms elapsed cpu time
    0 ms elapsed real time
    98584 bytes allocated
(1766 1246 1000 961 869)

We used hash tables and the identity function as in the previous example, as well as a split function, shown at codepad, that uses the tortoise-and-hare algorithm to split a list into front and back halves. You can run the program at http://programmingpraxis.codepad.org/Ea9JNyI9.

Pages: 1 2