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) |
2 soluciones de “Productos de elementos de dos conjuntos”