Pares a distancia dada
Definir la función
|
1 |
pares :: [Int] -> Int -> [(Int,Int)] |
tal que (pares xs k) es la lista de pares de elementos de xs que están a distancia k (se supone que los elementos de xs son distintos). Por ejemplo,
|
1 2 3 |
pares [1,5,3,4,2,8] 2 == [(1,3),(3,5),(2,4)] pares [1,2,7,9,6,5] 2 == [(5,7),(7,9)] length (pares [1..10^6] 3) == 999997 |
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
import Data.List (sort, tails) import Data.Set -- 1ª definición -- ============= pares1 :: [Int] -> Int -> [(Int,Int)] pares1 xs k = [(x,y) | x <- xs, y <- xs, y - x == k] -- 2ª definición -- ============= pares2 :: [Int] -> Int -> [(Int,Int)] pares2 xs k = [(y,y+k) | (y:ys) <- init (tails (sort xs)) , (y+k) `pertenece` ys] pertenece :: Int -> [Int] -> Bool pertenece _ [] = False pertenece x (y:ys) | x < y = False | x == y = True | otherwise = pertenece x ys -- 3ª definición -- ============= pares3 :: [Int] -> Int -> [(Int,Int)] pares3 xs k = [(x,x+k) | x <- xs , (x+k) `member` c] where c = fromList xs -- Comparación de eficiencia -- ========================= -- λ> length (pares1 [1..2000] 3) -- 1997 -- (4.26 secs, 471,640,672 bytes) -- λ> length (pares2 [1..2000] 3) -- 1997 -- (0.02 secs, 0 bytes) -- λ> length (pares3 [1..2000] 3) -- 1997 -- (0.01 secs, 0 bytes) -- -- λ> length (pares2 [1..10^6] 3) -- 999997 -- (6.00 secs, 855,807,112 bytes) -- λ> length (pares3 [1..10^6] 3) -- 999997 -- (3.67 secs, 390,934,904 bytes) |