Productos de elementos de dos conjuntos
Definir la función
|
1 |
productos :: [Integer] -> [Integer] -> Integer -> [(Integer,Integer)] |
tal que (productos as bs c) es la lista de pares (a,b) tales que a un elementos de as, b es un elemento de bs y su producto es x, donde as y bs son listas (posiblemente infinitas) ordenadas crecientes. Por ejemplo,
|
1 2 3 |
productos [3,5..] [2,4..] 2000 == [(5,400),(25,80),(125,16)] productos [3,5..] [2,4..] 2001 == [] length (productos [3,5..] [2,4..] (product [1..11])) == 59 |
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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
import Data.List (group, inits, nub, sort, subsequences) import Data.Numbers.Primes (primeFactors) -- 1ª solución -- =========== productos :: [Integer] -> [Integer] -> Integer -> [(Integer,Integer)] productos as bs c = [(a,b) | a <- takeWhile (<= c) as, c `mod` a == 0, let b = c `div` a, b `pertenece` bs] -- (pertenece x ys) se verifica si x pertenece a la lista ordenada -- creciente ys. Por ejemplo, -- pertenece 15 [1,3..] == True -- pertenece 16 [1,3..] == False pertenece :: Integer -> [Integer] -> Bool pertenece x ys = x == head (dropWhile (< x) ys) -- 2ª solución -- =========== productos2 :: [Integer] -> [Integer] -> Integer -> [(Integer,Integer)] productos2 as bs c = [(a,b) | a <- as', let b = c `div` a, b `pertenece` bs'] where cs = divisores c as' = interseccion cs (takeWhile (<=c) as) bs' = interseccion cs (takeWhile (<=c) bs) -- (divisores x) es el conjunto de divisores de los x. Por ejemplo, -- divisores 30 == [1,2,3,5,6,10,15,30] divisores :: Integer -> [Integer] divisores = sort . map (product . concat) . sequence . map inits . group . primeFactors -- (interseccion xs ys) es la intersección entre las listas ordenadas -- crecientes xs e ys. Por ejemplo, -- λ> take 10 (interseccion [1,3..] [2,5..]) -- [5,11,17,23,29,35,41,47,53,59] interseccion :: Ord a => [a] -> [a] -> [a] interseccion = aux where aux as@(x:xs) bs@(y:ys) = case compare x y of LT -> aux xs bs EQ -> x : aux xs ys GT -> aux as ys aux _ _ = [] -- 2ª solución -- =========== productos3 :: [Integer] -> [Integer] -> Integer -> [(Integer,Integer)] productos3 as bs c = aux as' bs' where aux (x:xs) (y:ys) | x * y == c = (x,y) : aux xs ys | x * y > c = aux (x:xs) ys | otherwise = aux xs (y:ys) aux _ _ = [] cs = divisores c as' = interseccion cs (takeWhile (<=c) as) bs' = reverse (interseccion cs (takeWhile (<=c) bs)) -- Comparación de eficiencia -- ========================= -- La compactación es -- λ> length (productos [3,5..] [2,4..] (product [1..11])) -- 59 -- (9.83 secs, 5,588,474,408 bytes) -- λ> length (productos2 [3,5..] [2,4..] (product [1..11])) -- 59 -- (10.48 secs, 8,942,746,480 bytes) -- λ> length (productos3 [3,5..] [2,4..] (product [1..11])) -- 59 -- (17.39 secs, 13,413,570,800 bytes) |
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>