Mínimo producto escalar
El producto escalar de los vectores [latex][a_1,a_2,\dots,a_n][/latex] y [latex][b_1,b_2,\dots,b_n][/latex] es [latex]a_1 \times b_1 + a_2 \times b_2 + \dots + a_n \times b_n[/latex].
Definir la función
menorProductoEscalar :: (Ord a, Num a) => [a] -> [a] -> a
tal que (menorProductoEscalar xs ys) es el mínimo de los productos escalares de las permutaciones de xs y de las permutaciones de ys. Por ejemplo,
menorProductoEscalar [3,2,5] [1,4,6] == 29 menorProductoEscalar [3,2,5] [1,4,-6] == -19 menorProductoEscalar [0..9] [0..9] == 120 menorProductoEscalar [0..99] [0..99] == 161700 menorProductoEscalar [0..999] [0..999] == 166167000
Soluciones
import Data.List (sort, permutations) -- 1ª definición menorProductoEscalar1 :: (Ord a, Num a) => [a] -> [a] -> a menorProductoEscalar1 xs ys = minimum [sum (zipWith (*) pxs ys) | pxs <- permutations xs] -- 2ª definición menorProductoEscalar2 :: (Ord a, Num a) => [a] -> [a] -> a menorProductoEscalar2 xs ys = sum (zipWith (*) (sort xs) (reverse (sort ys))) -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> menorProductoEscalar1 [0..9] [0..9] -- 120 -- (23.86 secs, 9342872784 bytes) -- -- λ> menorProductoEscalar2 [0..9] [0..9] -- 120 -- (0.01 secs, 2580824 bytes)