Menu Close

Pares a distancia dada

Definir la función

   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,

   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

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)

10 soluciones de “Pares a distancia dada

  1. albcercid
    import Data.Set 
     
    pares :: [Int] -> Int -> [(Int,Int)]
    pares xs k = aux xs (fromList xs)
      where aux [] t = []
            aux (y:ys) t | member (y+k) t = (y,y+k) : aux ys t
                         | otherwise      = aux ys t
  2. ignareeva
    pares :: [Int] -> Int -> [(Int,Int)]
    pares xs n = [(y,x) | x <- xs, y <- xs, x-y == n]
    • marmerzaf

      Aparece en orden inverso a la solucion del exercitium, se solucionaria de la siguiente manera:

      pares :: [Int] -> Int -> [(Int,Int)]
      pares xs k = [(x,y) | x <- xs , y <- xs , y-x == k]
  3. fraferpoy
    pares :: [Int] -> Int -> [(Int,Int)]
    pares [] k = []
    pares xs 0 = []
    pares xs k = [(a,b) | a  <- xs, b <- xs, b - a == k]
  4. marlobrip
    pares :: [Int] -> Int -> [(Int,Int)]
    pares xs k  = [(x,y) | x <- xs, y <- xs, y - x == k]
  5. alvfercen
    pares :: [Int] -> Int -> [(Int,Int)]
    pares xs 0 = []
    pares xs k = [(x,y) | x <- xs, y <- xs, y-x == k]
  6. enrnarbej
    import Data.Set
    import qualified Data.List as L
    import Prelude hiding (map)
     
    pares :: [Int] -> Int -> [(Int,Int)]
    pares xs k = zip ((toList . map (+(-k))) i) (toList i)
               where
                s = fromList xs
                i = (intersection s . map (+k)) s
     
    pares2 :: [Int] -> Int -> [(Int,Int)]
    pares2 xs k = L.foldl' (x y -> if (y+k) `member` s then (y,y+k):x else x) [] xs
                where s = fromList xs
  7. juacasnie
    import Data.List 
     
    pares :: [Int] -> Int -> [(Int,Int)]
    pares xs k = nub (concat [aux ys | ys <- permutations xs])
       where    aux [] = []
                aux (x:y:zs) | x-y == k = (y,x) : aux zs 
                             | otherwise = aux zs
  8. Juanjo Ortega (juaorture)
    import qualified Data.Set as S
     
    pares1 :: [Int] -> Int -> [(Int, Int)]
    pares1 xs = aux (length xs) xs
           where aux n (x:xs) k  | n == 0      = []
                                 | y `elem` xs = (x,y) : aux (n-1) (xs++[x]) k 
                                 | otherwise   = aux (n-1) (xs++[x]) k 
                                     where y = x + k
     
    pares2 :: [Int] -> Int -> [(Int, Int)]
    pares2 xs k = aux (fromList xs) xs k 
           where aux _ []     _          = []
                 aux s (z:zs) d | x `S.member` s = (z,x) : aux s zs k
                                | otherwise   = aux s zs k 
                                     where x = z + k

Escribe tu solución

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