Menu Close

Suma minimal de productos de pares de elementos consecutivos

José A. Alonso,

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

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

  1. Responder
    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. Responder
    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. Responder
    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
  5. Responder
    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
  6. Responder
    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
  7. Responder
    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
  8. Responder
    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.