{"id":5994,"date":"2021-01-21T06:52:12","date_gmt":"2021-01-21T04:52:12","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5994"},"modified":"2021-01-28T09:24:42","modified_gmt":"2021-01-28T07:24:42","slug":"clausura-respecto-del-valor-absoluto-de-las-diferencias","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/clausura-respecto-del-valor-absoluto-de-las-diferencias\/","title":{"rendered":"Clausura respecto del valor absoluto de las diferencias"},"content":{"rendered":"<p>Dado un conjunto de n\u00fameros 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\u00e9n es un elemento de T. Por ejemplo, si S = {12, 30}, entonces<\/p>\n<ul>\n<li>12 \u2208 T, porque 12 \u2208 S<\/li>\n<li>30 \u2208 T, porque 20 \u2208 S<\/li>\n<li>18 = |12 &#8211; 30| \u2208 T<\/li>\n<li>6 = |18 &#8211; 12| \u2208 T<\/li>\n<li>24 = |30 &#8211; 6| \u2208 T<\/li>\n<\/ul>\n<p>Por tanto, T = {12, 30, 18, 6, 24}.<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   clausura :: [Int] -> [Int]\n   longitudClausura :: [Int] -> Int\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(clausura xs) es la clausura del conjunto de enteros positivos xs respecto del valor absoluto de la diferencia de pares. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     clausura [12,30]  ==  [12,30,18,6,24]\n     clausura [3,5,2]  ==  [3,5,2,1,4]\n<\/pre>\n<ul>\n<li>(longitudClausura xs) es el n\u00famero de elementos de la clausura del conjunto de enteros positivos xs respecto del valor absoluto de la diferencia de pares. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     longitudClausura [12,30]        ==  5\n     longitudClausura [3,5,2]        ==  5\n     longitudClausura [3,23..10^6]   ==  999983\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (nub, sort, union)\nimport Test.QuickCheck\n\n-- Definici\u00f3n de clausura\n-- ======================\n\nclausura :: [Int] -> [Int]\nclausura xs\n  | contenida ys xs = xs\n  | otherwise       = clausura (union xs ys)\n  where ys = diferencias xs\n\n-- (diferencias xs) es el conjunto de los valores absolutos de las\n-- diferencias de pares de elementos distintos de xs. Por ejemplo,\n--    diferencias [3,7,11]  ==  [4,8]\ndiferencias :: [Int] -> [Int]\ndiferencias xs =\n  nub [x - y | x <- xs\n             , y <- xs\n             , x > y]\n\n-- (contenida xs ys) se verifica si la lista xs esta contenida en\n-- ys. Por ejemplo,\n--    contenida [2,3] [3,5,2]  ==  True\n--    contenida [2,3] [3,5,7]  ==  False\ncontenida :: [Int] -> [Int] -> Bool\ncontenida xs ys =\n  all (`elem` ys) xs\n\n-- 1\u00aa definici\u00f3n de longitudClausura\n-- =================================\n\nlongitudClausura :: [Int] -> Int\nlongitudClausura = length . clausura\n\n-- 2\u00aa definici\u00f3n de longitudClausura\n-- =================================\n\n--    longitudClausura2 [3,23..10^6]  ==  999983\nlongitudClausura2 :: [Int] -> Int\nlongitudClausura2 xs =\n  maximum xs `div` mcd xs\n\n-- (mcd xs) es el m\u00e1ximo com\u00fan divisor de los elememtos de xs. Por\n-- ejemplo,\n--    mcd [12, 60]      ==  12\n--    mcd [12, 60, 42]  ==  6\nmcd :: [Int] -> Int\nmcd = foldl1 gcd\n\n-- Equivalencia\n-- ============\n\n-- La propiedd de equivalencia es\nprop_clausura :: [Int] -> Property\nprop_clausura xs =\n  not (null xs) ==>\n  longitudClausura ys == longitudClausura2 ys\n  where ys = nub (map ((+1) . abs) xs)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_clausura\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> longitudClausura [3,23..10^3]\n--    983\n--    (2.22 secs, 239,761,904 bytes)\n--    \u03bb> longitudClausura2 [3,23..10^3]\n--    983\n--    (0.01 secs, 118,968 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Dado un conjunto de n\u00fameros 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\u00e9n es un elemento de&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[4],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5994"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=5994"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5994\/revisions"}],"predecessor-version":[{"id":6033,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5994\/revisions\/6033"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5994"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5994"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5994"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}