Menu Close

Día: 18 febrero, 2021

Máximos locales y sus posiciones

José A. Alonso---1 Comentario

Los máximos locales de [7,2,3,4,4,4,0,1,1,0,1,4,9] son el 4 (que se encuentra en la posición 3 (empezando a contar en 0)) y el 1 que se encuentra en la posición 7. En cada meseta, por ejemplo la formada por los tres 4 en las posiciones 3, 4 y 5, sólo se considera el primer elemento (en este caso, el de la posición 3) y se compara con el primero después de la meseta (en este caso, el 0 de la posición 6).

Los extremos de la lista no se consideran máximos locales. Por ejmplo, la listas [1,2,2,2,3] y [1,2,2,2,2] no tienen máximos locales.

Definir la función

   maximosLocales :: Ord a => [a] -> [(a,Int)]

tal que (maximosLocales xs) es la lista de los máximos locales de xs junto con sus posiciones. Por ejemplo,

   maximosLocales [7,2,3,4,4,4,0,1,1,0,1,4,9]  ==  [(4,3),(1,7)]
   maximosLocales [1,2,2,2,3]  ==  []
   maximosLocales [1,2,2,2,2]  ==  []

Soluciones

import Data.List (groupBy)
import Data.Function (on)
 
-- 1ª solución
-- ===========
 
maximosLocales1 :: Ord a => [a] -> [(a,Int)]
maximosLocales1 = aux . enumeradosSinMesetas
 where
   aux (x:y:z:xs) | y > x && y > z = y : aux (z:xs)
                  | otherwise      = aux (y:z:xs)
   aux _                           = []
 
-- (enumeradosSinMesetas xs) es la lista xs con los elementos enumerados
-- y eliminando las mesetas (es decir,la sucesión de elementos
-- iguales). Por ejemplo,
--    λ> enumeradosSinMesetas [7,7,2,2,7,4,4,4,2]
--    [(7,0),(2,2),(7,4),(4,5),(2,8)]
enumeradosSinMesetas :: Eq a => [a] -> [(a,Int)]
enumeradosSinMesetas xs = aux (zip xs [0..])
  where aux [] = []
        aux ((x,n):ps) = (x,n) : aux (dropWhile (\(y,_) -> y == x) ps)
 
-- Se puede definir sin recursión:
enumeradosSinMesetas2 :: Eq a => [a] -> [(a,Int)]
enumeradosSinMesetas2 xs =
  map head (groupBy (on (==) fst) (zip xs [0..]))
 
-- 2ª solución
-- ===========
 
maximosLocales2 :: Ord a => [a] -> [(a,Int)]
maximosLocales2 xs =
  [y | (x,y,z) <- zip3 ps (tail ps) (drop 2 ps), x < y && y > z]
  where ps = enumeradosSinMesetas xs

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
Seguir leyendo →