Suma minimal de productos de pares de elementos consecutivos
Al permutar los elementos de la lista [1,2,3,4] se obtienen los siguientes valores de la suma de pares de elementos consecutivos:
- 10, por ejemplo con [1,4,2,3] ya que 1×4+2×3 = 10
- 11, por ejemplo con [1,3,2,4] ya que 1×3+2×4 = 11
- 14, por ejemplo con [1,2,3,4] ya que 1×2+3×4 = 14
Por tanto, la mínima suma de los productos de elementos consecutivos en las permutaciones de [1,2,3,4] es 10 y una permutación con dicha suma es [1,4,2,3].
Definir las funciones
|
1 2 |
minimaSumaProductos :: (Num a, Ord a) => [a] -> a permutacionMinimal :: (Num a, Ord a) => [a] -> [a] |
tales que
- (minimaSumaProductos xs) es la mínima suma de los productos de elementos consecutivos en las permutaciones de lista xs, suponiendo que xs tiene un número par de elementos. Por ejemplo,
|
1 2 3 4 |
minimaSumaProductos [1..4] == 10 minimaSumaProductos [3,2,5,7,1,6] == 34 minimaSumaProductos [9,2,8,4,5,7,6,0] == 74 minimaSumaProductos [1,2,1,4,0,5,6,0] == 6 |
- (permutacionMinimal xs) es una permutación de xs cuya suma de productos de elementos consecutivos de xs es la mínima suma de los productos de elementos consecutivos en las permutaciones de lista xs, suponiendo que xs tiene un número par de elementos. Por ejemplo,
|
1 2 3 4 |
permutacionMinimal [1..4] == [1,4,3,2] permutacionMinimal [3,2,5,7,1,6] == [1,7,2,6,3,5] permutacionMinimal [9,2,8,4,5,7,6,0] == [0,9,2,8,4,7,5,6] permutacionMinimal [1,2,1,4,0,5,6,0] == [0,6,0,5,1,4,1,2] |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
import Data.List (sort, permutations) import Test.QuickCheck -- 1ª definición -- ============= minimaSumaProductos :: (Num a, Ord a) => [a] -> a minimaSumaProductos xs = minimum [sumaProductos ys | ys <- permutations xs] -- sumaProductos [3,2,1,4] == 10 -- sumaProductos [2,4,3,1] == 11 -- sumaProductos [1,2,3,4] == 14 sumaProductos :: (Num a, Ord a) => [a] -> a sumaProductos [] = 0 sumaProductos [x] = x sumaProductos (x:y:zs) = x*y + sumaProductos zs permutacionMinimal :: (Num a, Ord a) => [a] -> [a] permutacionMinimal xs = head [ys | ys <- yss , sumaProductos ys == m] where yss = permutations xs m = minimaSumaProductos xs -- 2ª definición -- ============= permutacionMinimal2 :: (Num a, Ord a) => [a] -> [a] permutacionMinimal2 xs = intercala ys (reverse zs) where n = length xs (ys,zs) = splitAt (n `div` 2) (sort xs) intercala :: [a] -> [a] -> [a] intercala xs ys = concat [[x,y] | (x,y) <- zip xs ys] minimaSumaProductos2 :: (Num a, Ord a) => [a] -> a minimaSumaProductos2 = sumaProductos . permutacionMinimal2 -- Equivalencia -- ============ prop_equivalencia :: [Int] -> Property prop_equivalencia xs = even (length xs) ==> minimaSumaProductos xs == minimaSumaProductos2 xs -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=10}) prop_equivalencia -- +++ OK, passed 100 tests. |