Los conjuntos finitos de n\u00fameros naturales se pueden enumerar como sigue<\/p>\n
\n 0: []\n 1: [0]\n 2: [1]\n 3: [1,0]\n 4: [2]\n 5: [2,0]\n 6: [2,1]\n 7: [2,1,0]\n 8: [3]\n 9: [3,0]\n 10: [3,1]\n 11: [3,1,0]\n 12: [3,2]\n 13: [3,2,0]\n 14: [3,2,1]\n 15: [3,2,1,0]\n 16: [4]\n 17: [4,0]\n 18: [4,1]\n 19: [4,1,0]\n<\/pre>\nen la que los elementos est\u00e1n ordenados de manera decreciente.<\/p>\n
Definir la constante<\/p>\n
\n enumeracionCFN :: [[Integer]]\n<\/pre>\ntal que sus elementos son los conjuntos de los n\u00fameros naturales con la ordenaci\u00f3n descrita anteriormente. Por ejemplo,<\/p>\n
\n \u03bb> take 20 enumeracionCFN\n [[],\n [0],\n [1],[1,0],\n [2],[2,0],[2,1],[2,1,0],\n [3],[3,0],[3,1],[3,1,0],[3,2],[3,2,0],[3,2,1],[3,2,1,0],\n [4],[4,0],[4,1],[4,1,0]]\n<\/pre>\nComprobar con QuickCheck que<\/p>\n
\nimport Data.List (genericLength, nub, sort)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nenumeracionCFN :: [[Integer]]\nenumeracionCFN = concatMap enumeracionCFNHasta [0..]\n\n-- (enumeracionCFNHasta n) es la lista de conjuntos con la enumeraci\u00f3n\n-- anterior cuyo primer elemento es n. Por ejemplo,\n-- \u03bb> enumeracionCFNHasta 1\n-- [[1],[1,0]]\n-- \u03bb> enumeracionCFNHasta 2\n-- [[2],[2,0],[2,1],[2,1,0]]\n-- \u03bb> enumeracionCFNHasta 3\n-- [[3],[3,0],[3,1],[3,1,0],[3,2],[3,2,0],[3,2,1],[3,2,1,0]]\nenumeracionCFNHasta :: Integer -> [[Integer]]\nenumeracionCFNHasta 0 = [[],[0]]\nenumeracionCFNHasta n =\n [n:xs | k <- [0..n-1], xs <- enumeracionCFNHasta k]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nenumeracionCFN2 :: [[Integer]]\nenumeracionCFN2 = [] : aux 0 [[]]\n where aux n xs = yss ++ aux (n+1) (xs ++ yss)\n where yss = map (n:) xs\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nenumeracionCFN3 :: [[Integer]]\nenumeracionCFN3 = map conjunto [0..]\n\n-- (conjunto n) es el conjunto en la posici\u00f3n n. Por ejemplo,\n-- conjunto 6 == [2,1]\nconjunto :: Integer -> [Integer]\nconjunto n = reverse [x | (x,y) <- zip [0..] (binario n), y == 1]\n\n-- (binario n) es la representaci\u00f3n binarioa del n\u00famero n (en orden\n-- inverso). Por ejemplo,\n-- binario 6 == [0,1,1]\nbinario :: Integer -> [Integer]\nbinario 0 = [0]\nbinario 1 = [1]\nbinario n = n `mod` 2 : binario (n `div` 2)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- \u03bb> enumeracionCFN !! (4*10^5)\n-- [18,17,12,11,9,7]\n-- (1.18 secs, 576,924,344 bytes)\n-- \u03bb> enumeracionCFN2 !! (4*10^5)\n-- [18,17,12,11,9,7]\n-- (0.10 secs, 72,399,784 bytes)\n-- \u03bb> enumeracionCFN3 !! (4*10^5)\n-- [18,17,12,11,9,7]\n-- (0.07 secs, 64,123,952 bytes)\n--\n-- \u03bb> enumeracionCFN2 !! (6*10^6)\n-- [22,20,19,17,16,15,11,10,8,7]\n-- (1.25 secs, 1,082,690,216 bytes)\n-- \u03bb> enumeracionCFN3 !! (6*10^6)\n-- [22,20,19,17,16,15,11,10,8,7]\n-- (0.38 secs, 960,134,256 bytes)\n\n-- Propiedades\n-- ===========\n\n-- La primera propiedad es\nprop_enumeracionCFN :: Int -> Property\nprop_enumeracionCFN n =\n n >= 0 ==> xs < ys\n where (xs:ys:_) = drop n enumeracionCFN\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_enumeracionCFN\n-- +++ OK, passed 100 tests.\n\n-- La segunda propiedad es\nprop_completa :: [Integer] -> Bool\nprop_completa xs =\n xs' `elem` enumeracionCFN\n where xs' = reverse (sort (nub (map abs xs)))\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheckWith (stdArgs {maxSize=15}) prop_completa\n-- +++ OK, passed 100 tests.\n<\/pre>\nPensamiento<\/h4>\n\nJunto al agua fr\u00eda,
\nen la senda clara,
\nsombra dar\u00e1 alg\u00fan d\u00eda,
\nese arbolillo en que nadie repara.<\/p>\n
Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"
Los conjuntos finitos de n\u00fameros naturales se pueden enumerar como sigue 0: [] 1: [0] 2: [1] 3: [1,0] 4: [2] 5: [2,0] 6: [2,1] 7: [2,1,0] 8: [3] 9: [3,0] 10: [3,1] 11: [3,1,0] 12: [3,2] 13: [3,2,0] 14: [3,2,1] 15: [3,2,1,0] 16: [4] 17: [4,0] 18: [4,1] 19: [4,1,0] en la que los…<\/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":[58,46,415,10,24,11,6,32,14],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5285"}],"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=5285"}],"version-history":[{"count":7,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5285\/revisions"}],"predecessor-version":[{"id":5328,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5285\/revisions\/5328"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5285"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5285"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5285"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}