Minimum Scalar Product
August 10, 2012
Today’s exercise comes to us from the practice round of Google Code Jam 2008.
You are given two vectors v1=(x1,x2,…,xn) and v2=(y1,y2,…,yn). The scalar product of these vectors is a single number, calculated as x1y1+x2y2+…+xnyn.
Suppose you are allowed to permute the coordinates of each vector as you wish. Choose two permutations such that the scalar product of your two new vectors is the smallest possible, and output that minimum scalar product.
Google gives two examples: the minimum scalar product of the two vectors (1 3 -5) and (-2 4 1) is -25, and the minimum scalar product of the two vectors (1 2 3 4 5) and (1 0 1 0 1) is 6.
Your task is to write a program that finds the minimum scalar product of two vectors. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
My Haskell solution (see http://bonsaicode.wordpress.com/2012/08/10/programming-praxis-minimum-scalar-product/ for a version with comments):
[…] Pages: 1 2 […]
Is there a simple proof of the assertion that this always works? I looked briefly but failed to find one on the web and I need to attend to other things. I did find some other pages that simply assert that this pair of permutations produces the minimum. I found a purported counter-example that failed to be a counter-example. And I wrote a test program, below, that seems to confirm the assertion by always returning an empty set of permutations (of the second vector) that produce an even smaller result. So I believe it but if there is a memorable proof, I’d like to know.
from itertools import permutations from operator import mul from random import sample def subminima(first, second): first, second = sorted(first), sorted(second, reverse = True) allegedminimumscalarproduct = sum(map(mul, first, second)) return { p for p in permutations(second) if sum(map(mul, first, p)) < allegedminimumscalarproduct } pop = tuple(range(-10, 11)) + tuple(range(-4, 5)) + tuple(range(-3, 4)) def test(): for _ in range(10): print(subminima(sample(pop, 5), sample(pop, 5)))It’s not a proof, but a simple observation is that the maximum scalar product is produced by multiplying the largest item from each vector, then the second largest, and so on; then the minimum scalar product is the opposite. I’ll ask at a couple of web sites I know.
perl6 version
sub min_scalar(@xs,@ys) { [+] @xs.sort <<*>> @ys.sort.reverse; } # test say min_scalar([1..5],[1,0,1,0,1]); # 6 say min_scalar([1,3,-5],[-2,4,1]); # -25Here's an attempt at a proof:
Consider two vectors:
A = <a_1, a_2, ..., a_n> sorted highest to lowest, so a_i >= a_j if i < j; and
B = <b_1, b_2, ..., b_n> sorted lowest to highest, so b_i <= b_j if i < j.
The scalar product (A dot B) of these two vectors is:
a_1*b_1 + a_2*b_2 + ... + a_i*b_i + ...
Assume there exist a B' in which the positions of b_i and b_j have been
exchanged so that:
A dot B' < A dot B
... + a_i*b_j + ... + a_j*b_i + ... < ... + a_i*b_i + ... + a_j*b_j + ...
all the terms in the '...' are the same on both sides, so this reduces to:
a_i*b_j + a_j*b_i < a_i*b_i + a_j*b_j
which can be rearranged:
a_i*(b_j - b_i) < a_j*(b_j - b_i)
By definition of B, b_i <= b_j for i < j.
If b_i == b_j, then B' == B, and (A dot B') == (A dot B).
If b_i < b_j, then (b_j - b_i) > 0, so:
a_i < a_j
This contradicts that A is sorted so that a_i >= a_j for i < j.
Therefore, the assumption must be false.
[…] today’s Programming Praxis exercise, our goal is to calculate the minimum scalar product of two vectors. […]
My Python solution:
def min_scalar_product(v1, v2):
return sum([x * y for x, y in zip(sorted(v1), sorted(v2, reverse=True))])
Min Scalar Product
My try in Common lisp
I asked at http://www.reddit.com/r/math/comments/xzsi8/minimum_scalar_product/ and got this answer from Luonos. I think that’s pretty much the same as Mike’s proof.
Requires -std=c++0x option when compiled with g++.
#include <iostream> #include <vector> #include <algorithm> template< class IT1, class IT2, class T = decltype ( typename std::iterator_traits<IT1>::value_type() * typename std::iterator_traits<IT2>::value_type() ) > T minimumScalarProduct( IT1 a, IT1 aend, IT2 b, IT2 bend, T init = 0 ) { typedef typename std::iterator_traits<IT1>::value_type IT1_ValueType; typedef typename std::iterator_traits<IT2>::value_type IT2_ValueType; std::vector< IT1_ValueType > va( a, aend ); std::vector< IT2_ValueType > vb( b, bend ); std::sort( std::begin(va), std::end(va) ); std::sort( std::begin(vb), std::end(vb), std::greater< IT2_ValueType >() ); return std::inner_product( std::begin(va), std::end(va), std::begin(vb), init ); } int main( int argc, char *argv[] ) { std::vector<int> a { 5, 4, 3, 2, 1 }; int b[] = { 1, 0, 1, 0, 1 }; std::cout << minimumScalarProduct( std::begin(a), std::end(a), std::begin(b), std::end(b) ) << std::endl; return 0; }A Go solution:
package main import ( "fmt" "sort" ) type Reverse struct { sort.Interface } func (r Reverse) Less(i, j int) bool { return r.Interface.Less(j, i) } func ScalarProduct(v1, v2 []int) int { p := 0 for i := 0; i < min(len(v1), len(v2)); i++ { p += v1[i] * v2[i] } return p } func min(a, b int) int { if a < b { return a } return b } func MinScalarProduct(v1, v2 []int) int { sort.Ints(v1) sort.Sort(Reverse{sort.IntSlice(v2)}) return ScalarProduct(v1, v2) } func main() { fmt.Printf("%d\n", MinScalarProduct([]int{1, 3, -5}, []int{-2, 4, 1})) fmt.Printf("%d\n", MinScalarProduct([]int{1, 2, 3, 4, 5}, []int{1, 0, 1, 0, 1})) }[…] 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. […]