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 a₁, a₂, …, a_n and b₁, b₂, …, b_n such that a₁b₁ + a₂b₂ + … + a_nb_n 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))
 -25

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

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