Menu Close

Entre dos conjuntos

José A. Alonso,

Se dice que un x número se encuentra entre dos conjuntos xs e ys si x es divisible por todos los elementos de xs y todos los elementos de zs son divisibles por x. Por ejemplo, 12 se encuentra entre los conjuntos {2, 6} y {24, 36}.

Definir la función

   entreDosConjuntos :: [Int] -> [Int] -> [Int]

tal que (entreDosConjuntos xs ys) es la lista de elementos entre xs e ys (se supone que xs e ys son listas no vacías de números enteros positivos). Por ejemplo,

   entreDosConjuntos [2,6] [24,36]     ==  [6,12]
   entreDosConjuntos [2,4] [32,16,96]  ==  [4,8,16]

Otros ejemplos

   λ> (xs,a) = ([1..15],product xs) 
   λ> length (entreDosConjuntos5 xs [a,2*a..10*a])
   270
   λ> (xs,a) = ([1..16],product xs) 
   λ> length (entreDosConjuntos5 xs [a,2*a..10*a])
   360

Soluciones

import Test.QuickCheck 
 
-- 1ª solución
-- ===========
 
entreDosConjuntos :: [Int] -> [Int] -> [Int]
entreDosConjuntos xs ys =
  [z | z <- [a..b]
     , and [z `mod` x == 0 | x <- xs]
     , and [y `mod` z == 0 | y <- ys]]
  where a = maximum xs
        b = minimum ys
 
-- 2ª solución
-- ===========
 
entreDosConjuntos2 :: [Int] -> [Int] -> [Int]
entreDosConjuntos2 xs ys =
  [z | z <- [a..b]
     , all (`divideA` z) xs
     , all (z `divideA`) ys]
  where a = mcmL xs
        b = mcdL ys
 
--    mcmL [2,3,18]  ==  18
--    mcmL [2,3,15]  ==  30
mcdL :: [Int] -> Int
mcdL [x]    = x
mcdL (x:xs) = gcd x (mcdL xs)
 
--    mcmL [12,30,18]  ==  6
--    mcmL [12,30,14]  ==  2
mcmL :: [Int] -> Int
mcmL [x]    = x
mcmL (x:xs) = lcm x (mcmL xs)
 
divideA :: Int -> Int -> Bool
divideA x y = y `mod` x == 0
 
-- 3ª solución
-- ===========
 
entreDosConjuntos3 :: [Int] -> [Int] -> [Int]
entreDosConjuntos3 xs ys =
  [z | z <- [a..b]
     , all (`divideA` z) xs
     , all (z `divideA`) ys]
  where a = mcmL2 xs
        b = mcdL2 ys
 
-- Definición equivalente
mcdL2 :: [Int] -> Int
mcdL2 = foldl1 gcd
 
-- Definición equivalente
mcmL2 :: [Int] -> Int
mcmL2 = foldl1 lcm
 
-- 4ª solución
-- ===========
 
entreDosConjuntos4 :: [Int] -> [Int] -> [Int]
entreDosConjuntos4 xs ys =
  [z | z <- [a,a+a..b]
     , z `divideA` b] 
  where a = mcmL2 xs
        b = mcdL2 ys
 
-- 5ª solución
-- ===========
 
entreDosConjuntos5 :: [Int] -> [Int] -> [Int]
entreDosConjuntos5 xs ys =
  filter (`divideA` b) [a,a+a..b]
  where a = mcmL2 xs
        b = mcdL2 ys
 
-- Equivalencia
-- ============
 
-- Para comprobar la equivalencia se define el tipo de listas no vacías
-- de números enteros positivos:
newtype ListaNoVaciaDePositivos = L [Int]
  deriving Show
 
-- genListaNoVaciaDePositivos es un generador de listas no vacióas de
-- enteros positivos. Por ejemplo,
--    λ> sample genListaNoVaciaDePositivos
--    L [1]
--    L [1,2,2]
--    L [4,3,4]
--    L [1,6,5,2,4]
--    L [2,8]
--    L [11]
--    L [13,2,3]
--    L [7,3,9,15,11,12,13,3,9,6,13,3]
--    L [16,2,11,10,6,5,16,4,1,15,9,11,8,15,2,15,7]
--    L [5,4,9,13,5,6,7]
--    L [7,4,6,12,2,11,6,14,14,13,14,11,6,2,18,8,16,2,13,9]
genListaNoVaciaDePositivos :: Gen ListaNoVaciaDePositivos
genListaNoVaciaDePositivos = do
  x  <- arbitrary
  xs <- arbitrary
  return (L (map ((+1) . abs) (x:xs)))
 
-- Generación arbitraria de listas no vacías de enteros positivos.
instance Arbitrary ListaNoVaciaDePositivos where
  arbitrary = genListaNoVaciaDePositivos
 
-- La propiedad es
prop_entreDosConjuntos_equiv ::
     ListaNoVaciaDePositivos
  -> ListaNoVaciaDePositivos
  -> Bool
prop_entreDosConjuntos_equiv (L xs) (L ys) =
  entreDosConjuntos xs ys == entreDosConjuntos2 xs ys &&
  entreDosConjuntos xs ys == entreDosConjuntos3 xs ys &&
  entreDosConjuntos xs ys == entreDosConjuntos4 xs ys &&
  entreDosConjuntos xs ys == entreDosConjuntos5 xs ys 
 
-- La comprobación es
--    λ> quickCheck prop_entreDosConjuntos_equiv
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
--    λ> (xs,a) = ([1..10],product xs) 
--    λ> length (entreDosConjuntos xs [a,2*a..10*a])
--    36
--    (5.08 secs, 4,035,689,200 bytes)
--    λ> length (entreDosConjuntos2 xs [a,2*a..10*a])
--    36
--    (3.75 secs, 2,471,534,072 bytes)
--    λ> length (entreDosConjuntos3 xs [a,2*a..10*a])
--    36
--    (3.73 secs, 2,471,528,664 bytes)
--    λ> length (entreDosConjuntos4 xs [a,2*a..10*a])
--    36
--    (0.01 secs, 442,152 bytes)
--    λ> length (entreDosConjuntos5 xs [a,2*a..10*a])
--    36
--    (0.00 secs, 374,824 bytes)

Referencia

Este ejercicio está basado en el problema Between two sets de HackerRank.

Pensamiento

Las razones no se transmiten, se engendran, por cooperación, en el diálogo.

Antonio Machado

Posted in Medio
Tagged , , , , , , , , ,

6 Comments

  1. Raúl Sánchez Moreno (rausanmor1)
    Responder 
    entreDosConjuntos :: [Int] -> [Int] -> [Int]
entreDosConjuntos xs ys=
  [x | x <- [1..last ys + 1], a x xs, b x ys]
  where a x xs = and [rem x y == 0 | y <- xs]
        b x xs = and [rem y x == 0 | y <- xs]
  2. frahidzam
    Responder 
    entreDosConjuntos :: [Int] -> [Int] -> [Int]
entreDosConjuntos xs ys =
  [x | x <- [last xs..head ys], xdivy x xs, ydivx x ys]
 
xdivy :: Int -> [Int] -> Bool
xdivy x xs = and [mod x y == 0 | y <- xs]
 
ydivx :: Int -> [Int] -> Bool
ydivx x xs = and [mod y x == 0 | y <- xs]
  3. luipromor
    Responder 
    import Data.List (intersect, isSubsequenceOf, sort)
 
entreDosConjuntos :: [Int] -> [Int] -> [Int]
entreDosConjuntos xs ys =
  [z | z <- aux (map factores ys)
     , isSubsequenceOf (sort xs) (factores z)]  
  where factores x   = [ y | y <- [1..x], mod x y == 0]
        aux [zs]     = zs
        aux (xs:xss) = intersect xs (aux xss)
  4. sermurgar
    Responder 
    entreDosConjuntos :: [Int] -> [Int] -> [Int]
entreDosConjuntos xs ys =
  [m | m <- [1..m]
     , xsDivideX xs m
     , xDivideYs ys m]
  where m = maximum (xs++ ys)
 
xsDivideX :: [Int] -> Int -> Bool
xsDivideX xs y = and [mod y m == 0 | m <- xs ]
 
xDivideYs :: [Int] -> Int -> Bool
xDivideYs xs y = and [mod m y == 0 | m <- xs ]
  5. ireprirod
    Responder 
    entreDosConjuntos :: [Int] -> [Int] -> [Int]
entreDosConjuntos xs ys =
  [x | x <- [maximum xs .. minimum ys]
     , divisible x xs
     , divide x ys]
 
divisible :: Int -> [Int]-> Bool
divisible x xs = and [mod x y == 0 | y <- xs]
 
divide :: Int -> [Int]-> Bool
divide x xs = and [mod y x == 0 | y <- xs]
  6. javmarcha1
    Responder 
    entreDosConjuntos :: [Int] -> [Int] -> [Int]
entreDosConjuntos xs ys =
  [x | x <- [maximum xs..minimum ys],
             and [rem x y == 0 | y <- xs],
             and [rem z x == 0 | z <- ys]]

Escribe tu solución

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