Menu Close

Mínima diferencia entre elementos de una lista

Definir la función

   minimaDiferencia :: (Num a, Ord a) => [a] -> a

tal que (minimaDiferencia xs) es el menor valor absoluto de las diferencias entre todos los pares de elementos de xs (que se supone que tiene al menos 2 elementos). Por ejemplo,

   minimaDiferencia [1,5,3,19,18,25]  ==  1
   minimaDiferencia [30,5,20,9]       ==  4
   minimaDiferencia [30,5,20,9,5]     ==  0
   minimaDiferencia [1..10^6]         ==  1

En el primer ejemplo la menor diferencia es 1 y se da entre los elementos 19 y 18; en el 2ª es 4 entre los elementos 5 y 9 y en la 3ª es 0 porque el elemento 5 está repetido.

Soluciones

import Data.List (delete, sort)
 
-- 1ª definición    
minimaDiferencia1 :: (Num a, Ord a) => [a] -> a
minimaDiferencia1 xs =
    minimum [abs (x - y) | x <- xs, y <- delete x xs]
 
-- 2ª definición    
minimaDiferencia2 :: (Num a, Ord a) => [a] -> a
minimaDiferencia2 [x,y]  = abs (x - y)
minimaDiferencia2 (x:xs) = min (minimum [abs (x - y) | y <- xs])
                               (minimaDiferencia2 xs)      
 
-- 3ª definición    
minimaDiferencia3 :: (Num a, Ord a) => [a] -> a
minimaDiferencia3 xs =
    minimum [y - x | (x,y) <- zip ys (tail ys)]
    where ys = sort xs
 
-- Comparación de eficiencia
--    λ> minimaDiferencia1 [1..2*10^3]
--    1
--    (3.47 secs, 1,419,790,688 bytes)
--    λ> minimaDiferencia2 [1..2*10^3]
--    1
--    (0.78 secs, 684,030,712 bytes)
--    λ> minimaDiferencia3 [1..2*10^3]
--    1
--    (0.02 secs, 0 bytes)
--    
--    λ> minimaDiferencia2 [1..5*10^3]
--    1
--    (5.14 secs, 4,233,952,776 bytes)
--    λ> minimaDiferencia3 [1..5*10^3]
--    1
--    (0.02 secs, 0 bytes)
Posted in Medio

7 Comments

  1. Paola Cabrera Perza
    import Data.List
     
    diferencia :: Num t => [t] -> [[t]]
    diferencia []=[]
    diferencia (x:xs) =[abs (x-y)|y<-xs] : diferencia xs
     
    minimaDiferencia :: (Num a, Ord a) => [a] -> a
    minimaDiferencia xs = head (sort (concat (diferencia xs))
  2. josejuan
    minimaDiferencia :: (Num a, Ord a)[a] → a
    minimaDiferencia = minimum(zipWith ⊟ ↩ tail) ∘ sort
  3. fracruzam
    import Data.List (sort)
     
    minimaDiferencia :: (Num a, Ord a) => [a] -> a
    minimaDiferencia zs@(_:_:_) = buscaMinimo (z:ys) (z-y)
      where (y:z:ys) = sort zs
            buscaMinimo :: (Num a, Ord a) => [a] -> a -> a
            buscaMinimo (x:y:xs) m | x == y    = 0
                                   | n <  m    = buscaMinimo (y:xs) n
                                   | otherwise = buscaMinimo (y:xs) m
              where n = y - x
            buscaMinimo _        m = m
    minimaDiferencia _  = error "La lista debe contener mas de un elemento"
  4. alvalvdom1
    import Data.List
     
    minimaDiferencia :: (Num a, Ord a) => [a] -> a
    minimaDiferencia xs = minimo (abs (a-b)) ys
                          where (a:b:ys) = sort xs
     
    minimo :: (Num a, Ord a) => a -> [a] -> a
    minimo d (x:y:xs) | z <= d = minimo z (y:xs)
                      | otherwise = minimo d (y:xs)
                      where z = abs (x-y)
    minimo d _ = d
  5. manvermor
    import Data.List (sort)
     
    minimaDiferencia :: (Num a, Ord a) => [a] -> a
    minimaDiferencia xs = minimum $ aux (sort xs)
          where aux [] = []
                aux [x] = [x]
                aux (x:y:xs) = (y-x) : aux (y:xs)
  6. erisan
    minimaDiferencia :: (Num a, Ord a) => [a] -> a
    minimaDiferencia xs = minimum [abs (x-y) | (x,y) <- listaDeElementos xs]
     
    listaDeElementos :: [t] -> [(t, t)]
    listaDeElementos [] = []
    listaDeElementos (x:xs) = [(x,y) | y <- xs] ++ listaDeElementos xs
  7. fatvilpiz
    minimaDiferencia xs = head (sort (todaslasrestas xs))
     
    todaslasrestas [x,y]  = [abs(x-y)]
    todaslasrestas (x:xs) = restas (x:xs) ++ todaslasrestas xs
     
    restas []         = []
    restas [x,y]      = [abs(x-y)]
    restas (x:y:z:xs) = abs (x-y) : restas (x:z:xs)

Escribe tu solución

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