Menu Close

Máximos locales y sus posiciones

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

Una solución de “Máximos locales y sus posiciones

  1. Rubén Muñoz Mkrtchian
    import Data.List (group)
     
    maximosLocales :: Ord a => [a] -> [(a,Int)]
    maximosLocales [] = []
    maximosLocales xs = aux m xss
      where xss = (group xs)
            m   = length (head xss)
     
    -- aux n xss nos permite asignar a cada máximo local su posición respecto a la
    -- lista a la que pertenece. Por ejemplo,
    --   λ> group [1,1,5,7,3,3,3,4,4,1]
    --   [[1,1],[5],[7],[3,3,3],[4,4],[1]]
    --   λ> aux 2 it
    --   [(7,3),(4,7)]
     
    aux :: Ord a => Int -> [[a]] -> [(a,Int)]
    aux n xss
      | length xss <= 2 = []
      | otherwise =
          if xs1 < xs2 && xs2 > xs3 then (head xs2,n) : aux m xss'
          else aux m xss'
            where m    = n + length xs2
                  xs1  = xss !! 0
                  xs2  = xss !! 1
                  xs3  = xss !! 2
                  xss' = tail xss

Leave a Reply

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