Menu Close

Productos de elementos de dos conjuntos

José A. Alonso---2 Comentarios

Definir la función

   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,

   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

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>

2 soluciones de “Productos de elementos de dos conjuntos”

  1. Responder
    Alejandro Garcia Alcaide 
    productos'' :: [Integer] -> [Integer] -> Integer -> [(Integer,Integer)]
productos'' as bs c = [(a,b) | a <- xs, b <- ys, a*b == c]
 where xs = takeWhile (<=c) as
       ys = takeWhile (<=c) bs
-- Sin embargo, podemos encontrar una solucion mas eficiente, definiendo b como
-- el cociente entre c y a. 
 
productos' :: [Integer] -> [Integer] -> Integer -> [(Integer,Integer)]
productos' as bs c =
  [(a,b) | a <- xs, let b = div c a, elem b (takeWhile (<=b) bs), a*b==c]
 where xs = takeWhile (<=c) as
 
-- Aunque con esta funcion lleguemos al resultado, esta no es muy eficiente
-- pues para el cálculo de:
-- length (productos' [3,5..] [2,4..] (product [1..11]))
-- se necesitan 62.37 secs, 16,350,716,424 bytes.
 
-- Intentemos mejorar un poco mas la definicion:
productos :: [Integer] -> [Integer] -> Integer -> [(Integer,Integer)]
productos as bs c =
  [(a,b) | a <- xs, let b = div c a, elem b (takeWhile (<=b) bs)]
 where xs = takeWhile (<=c) (divisibleEntre c as)
         where divisibleEntre _ [] = []
               divisibleEntre x xs =
                 [y | y <-  (takeWhile (<= x) xs), mod x y == 0]
 
-- Ahora, obtenemos:
-- length (productos [3,5..] [2,4..] (product [1..11]))  ==  59
-- (70.14 secs, 8,489,455,744 bytes)
  2. Responder
    Joaquín Infante Rodríguez 
    import Data.List
 
productos :: [Integer] -> [Integer] -> Integer -> [(Integer,Integer)]
productos [] bs c = []
productos as [] c = []
productos as bs c = aux as bs (divisores c) c
       where aux ps ts [] h     = []
             aux ps ts (z:zs) h | elem z (x:xs) && elem e (y:ys) = (z,e):aux (x:xs) (y:ys) zs h
                                | otherwise                      = aux (x:xs) (y:ys) zs h
                   where e = (div h z)
                         (x:xs) = takeWhile (<=h) ps
                         (y:ys) = takeWhile (<=h) ts
 
 
--Definición de divisores vista en clase
divisores :: Integer -> [Integer]
divisores = sort. posProduct . group . primeFactors
 
posProduct :: [[Integer]] -> [Integer]
posProduct []       = []
posProduct [xs]     = [(head xs)^k     | k<-[0..length xs]]
posProduct (xs:xss) = [(head xs)^k * e | k<-[0..length xs], e<-posProduct xss]

Leave a Reply

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