Minimum scalar product

Another post from Programming Praxis, this time we’re to figure out what is the minimum scalar product of two vectors. Basically, you want to rearrange two given lists a1, a2, …, an and b1, b2, …, bn such that a1b1 + a2b2 + … + anbn is minimized.

It turns out though that it’s a remarkably simple algorithm. Just sort the two vectors and reverse the second one:

(define (minimum-scalar-product l r)
  (apply + (map * (sort < l) (sort > r))))

This will assure that the largest and smallest elements are paired, up through the smallest and largest. I don’t have a proof handy, but it will always give a minimal solution:

~ (minimum-scalar-product '(1 3 -5) '(-2 4 1))

~ (minimum-scalar-product '(1 2 3 4 5) '(1 0 1 0 1))

Could be helpful if I ever interview at a company that asks this sort of interview question

By category

Leave a Reply