Programming Praxis

We implement the algorithms exactly as CLRS gave them. First, here are the two auxiliary functions:

(define (list-add xs n)
  (map (lambda (x) (+ n x)) xs))

(define (merge-no-dups xs ys)
  (let loop ((xs xs) (ys ys) (zs (list)))
    (cond ((and (null? xs) (null? ys)) (reverse zs))
          ((null? xs) (loop xs (cdr ys) (cons (car ys) zs)))
          ((null? ys) (loop (cdr xs) ys (cons (car xs) zs)))
          ((< (car xs) (car ys)) (loop (cdr xs) ys (cons (car xs) zs)))
          ((< (car ys) (car xs)) (loop xs (cdr ys) (cons (car ys) zs)))
          (else (loop (cdr xs) (cdr ys) (cons (car xs) zs))))))

Next is the exact algorithm. Our iteration is slightly different than CLRS, but achieves the same result:

(define (exact-subset-sum xs t)
  (let loop ((xs xs) (ls (list 0)))
    (if (null? xs) (apply max ls)
      (loop (cdr xs)
            (filter (lambda (x) (<= x t))
              (merge-no-dups ls (list-add ls (car xs))))))))

Here is the example from CLRS:

> (exact-subset-sum '(1 4 5) 10)
10
> (exact-subset-sum '(1 4 5) 8
6

The trim function also uses a slightly different iteration that CLRS. For my money, the Scheme version using lists is clearer than the CLSR pseudocode using arrays, because the auxiliary variable to track the length of the array is no longer needed, but you may not agree. Notice that we kept the last variable, even though it is not strictly needed either since it is the same as (car ls):

(define (trim xs d)
  (let loop ((last (car xs)) (xs (cdr xs)) (ls (list (car xs))))
    (if (null? xs) (reverse ls)
      (if (< (* last (+ 1 d)) (car xs))
          (loop (car xs) (cdr xs) (cons (car xs) ls))
          (loop last (cdr xs) ls)))))

Then the approximate algorithm is similar to the exact algorithm:

(define (approx-subset-sum xs t e)
  (let ((len (length xs)))
    (let loop ((xs xs) (ls (list 0)))
      (if (null? xs) (apply max ls)
        (loop (cdr xs)
              (filter (lambda (x) (<= x t))
                (trim (merge-no-dups ls (list-add ls (car xs)))
                      (/ e 2 len))))))))

And here are some examples:

> (approx-subset-sum '(101 102 104 201) 308 0.4)
302
> (approx-subset-sum '(101 102 104 201) 308 0.1)
307
> (exact-subset-sum '(101 102 104 201) 308)
307

You can run the program at http://programmingpraxis.codepad.org/gcOgY3rQ.

Pages: 1 2