En un ejercicio anterior se mostr\u00f3 que 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
Adem\u00e1s, se defini\u00f3 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>\nDefinir la funci\u00f3n<\/p>\n
\n posicion :: [Integer] -> Integer\n<\/pre>\ntal que (posicion xs) es la posici\u00f3n del conjunto finito de n\u00fameros naturales xs, representado por una lista decreciente, en enumeracionCFN. Por ejemplo,<\/p>\n
\n posicion [2,0] == 5\n posicion [2,1] == 6\n posicion [2,1,0] == 7\n posicion [0] == 1\n posicion [1,0] == 3\n posicion [2,1,0] == 7\n posicion [3,2,1,0] == 15\n posicion [4,3,2,1,0] == 31\n posicion [5,4,3,2,1,0] == 63\n length (show (posicion [3*10^7])) == 9030900\n<\/pre>\nComprobar con QuickCheck que para todo n\u00famero natural n,<\/p>\n
\n posicion [n,n-1..0] == 2^(n+1) - 1.\n<\/pre>\nSoluciones<\/h4>\n\nimport Data.List (genericLength, nub, sort)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nposicion :: [Integer] -> Integer\nposicion xs =\n genericLength (takeWhile (< xs) enumeracionCFN)\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\nposicion2 :: [Integer] -> Integer\nposicion2 [] = 0\nposicion2 (x:xs) = 2^x + posicion2 xs\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nposicion3 :: [Integer] -> Integer\nposicion3 = foldr (\\x -> (+) (2^x)) 0 \n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nposicion4 :: [Integer] -> Integer\nposicion4 xs = sum [2^x | x <- xs ]\n\n-- Equivalencia de las definiciones\n-- ================================\n\n-- La propiedad es\nprop_equiv :: [Integer] -> Bool\nprop_equiv xs =\n all (== posicion xs') [f xs' | f <- [ posicion2\n , posicion3\n , posicion4]]\n where xs' = reverse (sort (nub (map abs xs)))\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheckWith (stdArgs {maxSize=15}) prop_equiv\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> posicion [19,18,17,16,14,9,6]\n-- 1000000\n-- (2.61 secs, 1,754,265,776 bytes)\n-- \u03bb> posicion2 [19,18,17,16,14,9,6]\n-- 1000000\n-- (0.01 secs, 111,808 bytes)\n-- \u03bb> posicion3 [19,18,17,16,14,9,6]\n-- 1000000\n-- \u03bb> posicion4 [19,18,17,16,14,9,6]\n-- 1000000\n-- (0.01 secs, 111,704 bytes)\n\n-- \u03bb> length (show (posicion2 [3*10^7]))\n-- 9030900\n-- (2.06 secs, 571,911,304 bytes)\n-- \u03bb> length (show (posicion3 [3*10^7]))\n-- 9030900\n-- (2.06 secs, 571,911,544 bytes)\n-- \u03bb> length (show (posicion4 [3*10^7]))\n-- 9030900\n-- (2.05 secs, 571,911,464 bytes)\n\n-- Propiedad\n-- =========\n\n-- La propiedad es\nprop_posicion :: Integer -> Property\nprop_posicion n =\n n >= 0 ==> posicion3 [n,n-1..0] == 2^(n+1) - 1\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_posicion\n-- +++ OK, passed 100 tests.\n<\/pre>\nPensamiento<\/h4>\n\n\u00a1Volar sin alas donde todo es cielo!<\/p>\n
Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"
En un ejercicio anterior se mostr\u00f3 que 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:…<\/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,258,415,11,6,34,146],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5291"}],"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=5291"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5291\/revisions"}],"predecessor-version":[{"id":5332,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5291\/revisions\/5332"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5291"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5291"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5291"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}