Programming Praxis

We modify the problem statement to return all matching triplets, rather than just an arbitrary one of them. Let’s begin with the obvious brute-force algorithm:

(define (3sum-brute xs)
  (define (x n) (vector-ref xs n))
  (let ((len (vector-length xs)))
  (list-of (sort < (list (x i) (x j) (x k)))
    (i range len)
    (j range (+ i 1) len)
  (k range (+ j 1) len)
  (zero? (+ (x i) (x j) (x k))))))

> (3sum-brute '#(8 -25 4 10 -10 -7 2 -3))
((8 -10 2) (10 -7 -3))

We sort the individual triplets just to make them look nice.

There are two ways to improve that, one involving searching and the other involving sorting (isn’t it odd how often that choice arises?). The searching solution enters each array element in a hash table then chooses two items using two nested loops and searches the hash table for the negative of the sum of the two items; we use our new set datatype instead of a hash table, because we don’t need to associate a value with a key:

(define (3sum-search xs)
  (define (x n) (vector-ref xs n))
  (let ((s (make-set 97)) (len (vector-length xs)))
    (do ((i 0 (+ i 1))) ((= i len))
      (s 'adjoin (x i)))
    (list-of (sort < (list (x i) (x j) k))
      (i range len)
      (j range (+ i 1) len)
      (k is (- (+ (x i) (x j))))
      (s 'member? k))))

The output of 3sum-search is three times as long as it should be, since each triple appears with k in each of the three positions. We take a two-pronged approach to the problem; first, the triples are individually sorted (that’s the real reason we sorted them in the brute-force solution), then a prune function uses a set to keep only one copy of each triplet:

(define (prune xs)
  (let ((s (make-set 97)))
    (do ((xs xs (cdr xs))) ((null? xs))
      (s 'adjoin (car xs)))
    (s 'enlist)))

> (prune (3sum-search '#(8 -25 4 10 -10 -7 2 -3)))
((-7 -3 10) (-10 2 8))

The sorting solution first sorts the input array, then tests each item in the array searching for a zero triple in a manner reminiscent of binary search:

(define (3sum-sort xs)
  (vector-sort! xs cmp)
  (let ((len (vector-length xs)) (zs (list)))
    (define (x n) (vector-ref xs n))
    (do ((i 0 (+ i 1))) ((= i (- len 2)))
      (let loop ((lo (+ i 1)) (hi (- len 1)))
        (when (< lo hi)
          (let ((s (+ (x i) (x lo) (x hi))))
            (cond ((negative? s) (loop (+ lo 1) hi))
                  ((positive? s) (loop lo (- hi 1)))
                  (else (set! zs (cons (sort < (list (x i) (x lo) (x hi))) zs))))))))
    zs))

> (3sum-sort '#(8 -25 4 10 -10 -7 2 -3))
((-7 -3 10) (-10 2 8))

We used list comprehensions and the Bentley-McIlroy vector sort from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/zW0EmC9m.

Pages: 1 2