Minimum Scalar Product

August 10, 2012

We begin with a function to compute the sum of the pair-wise products of two vectors, which we represent as lists:

(define (scalar xs ys) (sum (map * xs ys)))

Then the minimum scalar product is found when one vector is sorted in increasing order and the other vector is sorted in decreasing order; there is no need to generate and test all possible permutations:

(define (msp xs ys) (scalar (sort < xs) (sort > ys)))

Here are the two sample problems:

> (msp '(1 3 -5) '(-2 4 1))
-25
> (msp '(1 2 3 4 5) '(1 0 1 0 1))
6

We used sum and sort from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/ucF1geyn.

About these ads

Pages: 1 2

14 Responses to “Minimum Scalar Product”

  1. My Haskell solution (see http://bonsaicode.wordpress.com/2012/08/10/programming-praxis-minimum-scalar-product/ for a version with comments):

    import Data.List
    
    minScalar :: (Ord a, Num a) => [a] -> [a] -> a
    minScalar a = sum . zipWith (*) (sort a) . reverse . sort
    
  2. Jussi Piitulainen said

    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)))
    
  3. programmingpraxis said

    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.

  4. swuecho said

    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]);  # -25
    
  5. Mike said


    Here'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.

  6. [...] today’s Programming Praxis exercise, our goal is to calculate the minimum scalar product of two vectors. [...]

  7. infgeoax said

    My Python solution:

    def min_scalar_product(v1, v2):
    return sum([x * y for x, y in zip(sorted(v1), sorted(v2, reverse=True))])

  8. programmingpraxis said

    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.

  9. madscifi said

    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;
    }
    
  10. 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}))
    }
    
    
  11. [...] 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. [...]

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 600 other followers

%d bloggers like this: