Subset Sum, Meet In The Middle

March 30, 2012

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.

About these ads

Pages: 1 2

One Response to “Subset Sum, Meet In The Middle”

  1. Mike said

    Kinda quiet this week.

    Here’s a Python 2.7 solution:

    def subsetsum(nums, tgt):
        sums = {}
        for n in nums[::2]:
            for k,v in sums.items() + [(0,[])]:
                newsum = k + n
                if newsum not in sums:
                    sums[newsum] = v + [n]
                    if newsum == tgt:
                        return sums[tgt]
    
        difs = {tgt:[]}
        for n in nums[1::2]:
            for k,v in difs.items():
                newdif = k - n
                if newdif not in difs:
                    difs[newdif] = v + [n]
                    if newdif in sums:
                        return sums[newdif] + difs[newdif]
    
        return []
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 616 other followers

%d bloggers like this: