Menu Close

Mínima diferencia entre elementos de una lista

José A. Alonso,

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

7 Comments

  1. Paola Cabrera Perza
    Responder 
    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
    Responder 
    minimaDiferencia :: (Num a, Ord a) ⇒ [a] → a
minimaDiferencia = minimum ∘ (zipWith ⊟ ↩ tail) ∘ sort
  3. fracruzam
    Responder 
    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
    Responder 
    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
    Responder 
    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
    Responder 
    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
    Responder 
    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.