Ir al contenido principal

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)