Mínima diferencia entre elementos de una lista
Definir la función
|
1 |
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,
|
1 2 3 4 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
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) |