Pares a distancia dada

PorJosé A. Alonso 8-mayo-201715-mayo-2017

Definir la función

   pares :: [Int] -> Int -> [(Int,Int)]

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,

   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

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)

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 Comentarios

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

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

Responder

ignareeva dice:

8-mayo-2017 a las 08:17

Haskell

pares :: [Int] -> Int -> [(Int,Int)] pares xs n = [(y,x) | x <- xs, y <- xs, x-y == n]

1
2

pares :: [Int] -> Int -> [(Int,Int)]
pares xs n = [(y,x) | x <- xs, y <- xs, x-y == n]

Responder
1. marmerzaf dice:
  
  8-mayo-2017 a las 10:39
  
  Aparece en orden inverso a la solucion del exercitium, se solucionaria de la siguiente manera:
  
  Haskell
  
  pares :: [Int] -> Int -> [(Int,Int)] pares xs k = [(x,y) | x <- xs , y <- xs , y-x == k]
  
  1
  2
  
  pares :: [Int] -> Int -> [(Int,Int)]
  pares xs k = [(x,y) | x <- xs , y <- xs , y-x == k]
  
  Responder
fraferpoy dice:

8-mayo-2017 a las 08:33

Haskell

pares :: [Int] -> Int -> [(Int,Int)] pares [] k = [] pares xs 0 = [] pares xs k = [(a,b) | a <- xs, b <- xs, b - a == k]

1
2
3
4

pares :: [Int] -> Int -> [(Int,Int)]
pares [] k = []
pares xs 0 = []
pares xs k = [(a,b) | a <- xs, b <- xs, b - a == k]

Responder
1. antlopgom2 dice:
  
  8-mayo-2017 a las 13:32
  
  Se puede simplificar quitando los dos primeros casos
  
  Responder
marlobrip dice:

8-mayo-2017 a las 15:17

Haskell

pares :: [Int] -> Int -> [(Int,Int)] pares xs k = [(x,y) | x <- xs, y <- xs, y - x == k]

1
2

pares :: [Int] -> Int -> [(Int,Int)]
pares xs k = [(x,y) | x <- xs, y <- xs, y - x == k]

Responder
alvfercen dice:

8-mayo-2017 a las 16:18

Haskell

pares :: [Int] -> Int -> [(Int,Int)] pares xs 0 = [] pares xs k = [(x,y) | x <- xs, y <- xs, y-x == k]

1
2
3

pares :: [Int] -> Int -> [(Int,Int)]
pares xs 0 = []
pares xs k = [(x,y) | x <- xs, y <- xs, y-x == k]

Responder

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

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

Responder

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

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

Responder

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

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

Responder

Pares a distancia dada

Soluciones

10 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

10 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico