El producto escalar de los vectores [a1,a2,…,an] y [b1,b2,…, bn] es<\/p>\n
\n a1 * b1 + a2 * b2 + \u00b7\u00b7\u00b7 + an * bn.\n<\/pre>\nDefinir la funci\u00f3n<\/p>\n
\n menorProductoEscalar :: (Ord a, Num a) => [a] -> [a] -> a\n<\/pre>\ntal que (menorProductoEscalar xs ys)<\/code> es el m\u00ednimo de los productos escalares de las permutaciones de xs<\/code> y de las permutaciones de ys<\/code>. Por ejemplo,<\/p>\n\n menorProductoEscalar [3,2,5] [1,4,6] == 29\n menorProductoEscalar [3,2,5] [1,4,-6] == -19\n menorProductoEscalar [1..10^2] [1..10^2] == 171700\n menorProductoEscalar [1..10^3] [1..10^3] == 167167000\n menorProductoEscalar [1..10^4] [1..10^4] == 166716670000\n menorProductoEscalar [1..10^5] [1..10^5] == 166671666700000\n menorProductoEscalar [1..10^6] [1..10^6] == 166667166667000000\n<\/pre>\nSoluciones<\/h4>\n\nmodule Minimo_producto_escalar where\n\nimport Data.List (sort, permutations)\nimport Test.QuickCheck (quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nmenorProductoEscalar1 :: (Ord a, Num a) => [a] -> [a] -> a\nmenorProductoEscalar1 xs ys =\n minimum [sum (zipWith (*) pxs pys) | pxs <- permutations xs,\n pys <- permutations ys]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nmenorProductoEscalar2 :: (Ord a, Num a) => [a] -> [a] -> a\nmenorProductoEscalar2 xs ys =\n minimum [sum (zipWith (*) pxs ys) | pxs <- permutations xs]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nmenorProductoEscalar3 :: (Ord a, Num a) => [a] -> [a] -> a\nmenorProductoEscalar3 xs ys =\n sum (zipWith (*) (sort xs) (reverse (sort ys)))\n\n-- Equivalencia\n-- ============\n\n-- La propiedad es\nprop_menorProductoEscalar :: [Integer] -> [Integer] -> Bool\nprop_menorProductoEscalar xs ys =\n all (== menorProductoEscalar1 xs' ys')\n [menorProductoEscalar2 xs' ys',\n menorProductoEscalar3 xs' ys']\n where n = min (length xs) (length ys)\n xs' = take n xs\n ys' = take n ys\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheckWith (stdArgs {maxSize=7}) prop_menorProductoEscalar\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> menorProductoEscalar1 [0..5] [0..5]\n-- 20\n-- (3.24 secs, 977385528 bytes)\n-- \u03bb> menorProductoEscalar2 [0..5] [0..5]\n-- 20\n-- (0.01 secs, 4185776 bytes)\n--\n-- \u03bb> menorProductoEscalar2 [0..9] [0..9]\n-- 120\n-- (23.86 secs, 9342872784 bytes)\n-- \u03bb> menorProductoEscalar3 [0..9] [0..9]\n-- 120\n-- (0.01 secs, 2580824 bytes)\n--\n-- \u03bb> menorProductoEscalar3 [0..10^6] [0..10^6]\n-- 166666666666500000\n-- (2.46 secs, 473,338,912 bytes)\n<\/pre>\n