Menu Close

Elementos con su doble en el conjunto

José A. Alonso,

Definir la función

   conDoble :: [Int] -> [Int]

tal que (conDoble xs) es la lista de los elementos del conjunto xs (representado como una lista sin elementos repetidos) cuyo doble pertenece a xs. Por ejemplo,

   conDoble [1, 4, 3, 2, 9, 7, 18, 22]  ==  [1,2,9]
   conDoble [2, 4, 8, 10]               ==  [2,4]
   conDoble [7, 5, 11, 13, 1, 3]        ==  []
   length (conDoble4 [1..10^6])         ==  500000

Referencia: Basado en el problema Doubles de POJ (Peking University Online Judge System).

Soluciones

import Data.List (intersect, sort)
import qualified Data.Set as S
 
-- 1ª Definición
conDoble :: [Int] -> [Int]
conDoble xs =
  [x | x <- xs, 2 * x `elem` xs]
 
-- 2ª Definición
conDoble2 :: [Int] -> [Int]
conDoble2 xs = aux (sort xs)
  where aux [] = []
        aux (y:ys) | 2 * y `elem` xs = y : aux ys
                   | otherwise       = aux ys
 
-- 3ª definición
conDoble3 :: [Int] -> [Int]
conDoble3 xs =
  sort (map (`div` 2) (xs `intersect` (map (*2) xs)))
 
-- 4ª definición
conDoble4 :: [Int] -> [Int]
conDoble4 xs =
  S.toList (S.map (`div` 2) (ys `S.intersection` (S.map (*2) ys)))
  where ys = S.fromList xs
 
-- Comparación de eficiencia
--    λ> length (conDoble [1..10^4])
--    5000
--    (3.27 secs, 0 bytes)
--    λ> length (conDoble2 [1..10^4])
--    5000
--    (3.42 secs, 0 bytes)
--    λ> length (conDoble3 [1..10^4])
--    5000
--    (4.78 secs, 0 bytes)
--    λ> length (conDoble4 [1..10^4])
--    5000
--    (0.02 secs, 0 bytes)
Posted in Inicial
Tagged , , , , , , , , , , , ,

9 Comments

  1. Daniel
    Responder 
    conDoble :: [Int] -> [Int]
conDoble xs = [x | x <- xs , elem (2*x) xs]
  2. marmerzaf
    Responder 
    conDoble :: [Int] -> [Int]
 
conDoble [] = []
conDoble (x:xs)  | 2*x `elem` xs = x : conDoble xs
                 | otherwise =  conDoble xs
  3. paumacpar
    Responder 
    import Data.Set
 
conDoble :: [Int] -> [Int]
conDoble xs = aux xs (fromList xs) []
  where aux [] c ys = ys 
        aux (x:xs) c ys | member (2*x) c = aux xs c (x:ys)
                        | otherwise = aux xs c ys
  4. marlobrip
    Responder 
    conDoble :: [Int] -> [Int]
conDoble xs = [ x | x <- xs , 2*x `elem` xs]
  5. enrnarbej
    Responder 
    import qualified Data.Set as S
 
conDoble :: [Int] -> [Int]
conDoble xs = (S.toList . S.intersection b . S.fromList) xs
            where
             a = filter even xs
             b = (S.fromList . map (`div` 2)) a
  6. albcercid
    Responder 
     
conDoble :: [Int] -> [Int]                
conDoble xs = filter (x -> S.member (2*x) t) xs
     where t = S.fromList (filter even xs)
  7. Miguel Ibáñez (migibagar)
    Responder 
    conDoble :: [Int] -> [Int]
conDoble xs = aux xs xs []
  where aux _  [] zs     = zs
        aux ys (x:xs) zs | prop x ys  =  aux ys xs ((x `div` 2) : zs)
                         | otherwise  =  aux ys xs zs
 
prop :: Int -> [Int] -> Bool
prop x xs = a `elem` xs && b == 0
  where (a,b) = quotRem x 2
 
-- Muy poco eficiente
  8. natmarmar2
    Responder 
    conDoble :: [Int] -> [Int]
conDoble [] = []
conDoble xs = [ x | x <- xs , y <- xs , y == 2*x]

Escribe tu solución

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