Menu Close

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

   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,
     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,
     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

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.

8 soluciones de “Suma minimal de productos de pares de elementos consecutivos

  1. enrnarbej
    minimaSumaProductos :: (Num a, Ord a) => [a] -> a
    minimaSumaProductos xs = sum $ zipWith (*) as (reverse bs)
      where (as, bs) = splitAt (length xs `div` 2) (sort xs)
     
    permutacionMinimal :: (Num a, Ord a) => [a] -> [a]
    permutacionMinimal xs = concat $ zipWith (x y -> [x,y]) as (reverse bs)
      where (as, bs) = splitAt (length xs `div` 2) (sort xs)
  2. Chema Cortés

    Una primera versión (sin optimizar):

    import Data.List (minimumBy, permutations)
    import Data.Function (on)
     
    minimaSumaProductos :: (Num a, Ord a) => [a] -> a
    minimaSumaProductos = sumaProductos . permutacionMinimal
     
    permutacionMinimal :: (Num a, Ord a) => [a] -> [a]
    permutacionMinimal = minimumBy (compare `on` sumaProductos) . permutations
     
    sumaProductos :: Num a => [a] -> a
    sumaProductos (x:y:xs) = x*y + sumaProductos xs
    sumaProductos _ = 0
  3. albcercid

    El razonamiento se basa en que los números más grandes se deben unir con los más pequeños.
    Como nx = x+x…+x (n veces), es recomendable multiplicar x por el número más pequeño posible, para que x se sume el mínimo de veces.

    permutacionMinimal   :: (Num a, Ord a) => [a] -> [a]
    permutacionMinimal xs = take (length xs) (aux p (reverse p))
      where p                 = sort xs
            aux [] _          = []
            aux (x:xs) (y:ys) = x:y:aux xs ys
     
    minimaSumaProductos  :: (Num a, Ord a) => [a] -> a
    minimaSumaProductos xs = aux (permutacionMinimal xs)
      where aux []       = 0
            aux (x:y:xs) = x*y + aux xs
  4. eliguivil
    minimaSumaProductos :: (Num a, Ord a) => [a] -> a
    minimaSumaProductos [] = 0
    minimaSumaProductos xs 
      | (odd . length) xs = aux $ une (separa xs)
      | otherwise         = aux $ sort xs
      where
       aux []     = 0
       aux (x:xs) = x * last xs + aux (init xs)
     
    permutacionMinimal :: (Num a, Ord a) => [a] -> [a]
    permutacionMinimal xs
      | (odd . length) xs = aux $ une (separa xs)
      | otherwise         = aux (sort xs)
      where
        aux []     = []
        aux (x:xs) = x : last xs : aux (init xs)
     
    separa xs = splitAt (length xs `div` 2) (sort xs)
     
    une (xs, y:ys) = xs ++ ys
  5. Chema Cortés
    import Data.List
     
    minimaSumaProductos :: (Num a, Ord a) => [a] -> a
    minimaSumaProductos = sumaProductos . permutacionMinimal
     
    sumaProductos :: Num a => [a] -> a
    sumaProductos (x:y:xs) = x*y + sumaProductos xs
    sumaProductos _ = 0
     
    permutacionMinimal :: (Num a, Ord a) => [a] -> [a]
    permutacionMinimal [] = []
    permutacionMinimal xs = take (length xs')
                          $ concat [[x,y] | (x,y) <- zip xs' (reverse xs')]
      where
        -- xs' elimina el mayor elemento cuando tiene longitud impar
        xs' | (odd.length) xs = init (sort xs)
            | otherwise       = sort xs
  6. paumacpar
    minimaSumaProductosA6 :: (Num a, Ord a) => [a] -> a
    minimaSumaProductosA6 xs = productos (permutacionMinimalA6 xs)
     
    permutacionMinimalA6 :: (Num a, Ord a) => [a] -> [a]
    permutacionMinimalA6 [] = []
    permutacionMinimalA6 xs =
      z : y : permutacionMinimalA6 (delete z (delete y xs))
      where z = minimum xs
            y = maximum xs 
     
    productos :: (Num a, Ord a) => [a] -> a
    productos xs = sum (zipWith (*) (pares xs) (impares xs))
     
    pares :: [a] -> [a]
    pares []     = []
    pares (x:xs) = x : impares xs
     
    impares :: [a] -> [a]
    impares []     = []
    impares (_:xs) = pares xs
  7. Juanjo Ortega (juaorture)
    import Data.List
     
    opera :: Num a => [a] -> a
    opera []       = 0
    opera (x:y:xs) = x*y + opera xs
     
    permutacionMinimal :: (Num a, Ord a) => [a] -> [a]
    permutacionMinimal [] = []
    permutacionMinimal xs = y : l : permutacionMinimal (xs[y,l])
                       where (y:ys) = sort xs
                             l      = last ys
     
    minimaSumaProductos :: (Num a, Ord a) => [a] -> a
    minimaSumaProductos xs = opera (permutacionMinimal xs)

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.