Menu Close

Clausura respecto del valor absoluto de las diferencias

 

Dado un conjunto de números enteros positivos S su clausura del valor absoluto de la diferencia de pares es el menor conjunto T tal que T contiene a S y para cualquier par de elementos x e y de T (con x distinto de y) el valor absoluto de (x-y) también es un elemento de T. Por ejemplo, si S = {12, 30}, entonces

  • 12 ∈ T, porque 12 ∈ S
  • 30 ∈ T, porque 20 ∈ S
  • 18 = |12 – 30| ∈ T
  • 6 = |18 – 12| ∈ T
  • 24 = |30 – 6| ∈ T

Por tanto, T = {12, 30, 18, 6, 24}.

Definir las funciones

   clausura :: [Int] -> [Int]
   longitudClausura :: [Int] -> Int

tales que

  • (clausura xs) es la clausura del conjunto de enteros positivos xs respecto del valor absoluto de la diferencia de pares. Por ejemplo,
     clausura [12,30]  ==  [12,30,18,6,24]
     clausura [3,5,2]  ==  [3,5,2,1,4]
  • (longitudClausura xs) es el número de elementos de la clausura del conjunto de enteros positivos xs respecto del valor absoluto de la diferencia de pares. Por ejemplo,
     longitudClausura [12,30]        ==  5
     longitudClausura [3,5,2]        ==  5
     longitudClausura [3,23..10^6]   ==  999983

Soluciones

import Data.List (nub, sort, union)
import Test.QuickCheck
 
-- Definición de clausura
-- ======================
 
clausura :: [Int] -> [Int]
clausura xs
  | contenida ys xs = xs
  | otherwise       = clausura (union xs ys)
  where ys = diferencias xs
 
-- (diferencias xs) es el conjunto de los valores absolutos de las
-- diferencias de pares de elementos distintos de xs. Por ejemplo,
--    diferencias [3,7,11]  ==  [4,8]
diferencias :: [Int] -> [Int]
diferencias xs =
  nub [x - y | x <- xs
             , y <- xs
             , x > y]
 
-- (contenida xs ys) se verifica si la lista xs esta contenida en
-- ys. Por ejemplo,
--    contenida [2,3] [3,5,2]  ==  True
--    contenida [2,3] [3,5,7]  ==  False
contenida :: [Int] -> [Int] -> Bool
contenida xs ys =
  all (`elem` ys) xs
 
-- 1ª definición de longitudClausura
-- =================================
 
longitudClausura :: [Int] -> Int
longitudClausura = length . clausura
 
-- 2ª definición de longitudClausura
-- =================================
 
--    longitudClausura2 [3,23..10^6]  ==  999983
longitudClausura2 :: [Int] -> Int
longitudClausura2 xs =
  maximum xs `div` mcd xs
 
-- (mcd xs) es el máximo común divisor de los elememtos de xs. Por
-- ejemplo,
--    mcd [12, 60]      ==  12
--    mcd [12, 60, 42]  ==  6
mcd :: [Int] -> Int
mcd = foldl1 gcd
 
-- Equivalencia
-- ============
 
-- La propiedd de equivalencia es
prop_clausura :: [Int] -> Property
prop_clausura xs =
  not (null xs) ==>
  longitudClausura ys == longitudClausura2 ys
  where ys = nub (map ((+1) . abs) xs)
 
-- La comprobación es
--    λ> quickCheck prop_clausura
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> longitudClausura [3,23..10^3]
--    983
--    (2.22 secs, 239,761,904 bytes)
--    λ> longitudClausura2 [3,23..10^3]
--    983
--    (0.01 secs, 118,968 bytes)
Medio

Una solución de “Clausura respecto del valor absoluto de las diferencias

  1. Ángel Ruiz
    import Data.List       (nub,foldl')
    import Test.QuickCheck (quickCheck)
     
    clausura :: [Int] -> [Int]
    clausura = until ((==) <*> (nub . f)) (nub . f)
      where f (x:xs) = x:(f xs) ++ map (abs . (x -)) xs
            f _      = []
     
    -- 1ª definición
    longitudClausura1 :: [Int] -> Int
    longitudClausura1 = length . clausura
     
    -- 2ª definición
    longitudClausura2 :: [Int] -> Int
    longitudClausura2 ys@(x:xs) = maximum ys `div` foldl' gcd x xs
    longitudClausura2 _         = 0
     
    -- Comparación de eficiencia
    -- =========================
     
    -- λ> longitudClausura1 [3,23..10^2]
    -- 83
    -- (0.20 secs, 9,913,528 bytes)
    -- λ> longitudClausura2 [3,23..10^2]
    -- 83
    -- (0.03 secs, 81,928 bytes)
     
    -- Equivalencia de las soluciones
    -- =============================
     
    -- La propiedad es
    prop_equiv :: [Int] -> Bool
    prop_equiv xs = longitudClausura1 ys == longitudClausura2 ys
      where ys = filter (> 0) (nub xs)
     
    -- La comprobación es
    --    λ> quickCheck prop_equiv
    --    +++ OK, passed 100 tests.

Leave a Reply

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