{"id":4046,"date":"2018-05-08T06:00:40","date_gmt":"2018-05-08T04:00:40","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=4046"},"modified":"2018-05-15T06:13:21","modified_gmt":"2018-05-15T04:13:21","slug":"numeros-construidos-con-los-digitos-de-un-conjunto-dado","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/numeros-construidos-con-los-digitos-de-un-conjunto-dado\/","title":{"rendered":"N\u00fameros construidos con los d\u00edgitos de un conjunto dado"},"content":{"rendered":"<p>Definir las siguientes funciones<\/p>\n<pre lang=\"text\">\n   numerosCon      :: [Integer] -> [Integer]\n   numeroDeDigitos :: [Integer] -> Integer -> Int\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(numerosCon ds) es la lista de los n\u00fameros que se pueden construir con los d\u00edgitos de ds (cuyos elementos son distintos elementos del 1 al 9) . Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> take 22 (numerosCon [1,4,6,9])\n     [1,4,6,9,11,14,16,19,41,44,46,49,61,64,66,69,91,94,96,99,111,114]\n     \u03bb> take 15 (numerosCon [4,6,9])\n     [4,6,9,44,46,49,64,66,69,94,96,99,444,446,449]\n     \u03bb> take 15 (numerosCon [6,9])\n     [6,9,66,69,96,99,666,669,696,699,966,969,996,999,6666]\n<\/pre>\n<ul>\n<li>(numeroDeDigitos ds k) es el n\u00famero de d\u00edgitos que tiene el k-\u00e9simo elemento (empezando a contar en 0) de la sucesi\u00f3n (numerosCon ds). Por ejemplo,    <\/li>\n<\/ul>\n<pre lang=\"text\">\n     numeroDeDigitos [1,4,6,9]   3  ==  1\n     numeroDeDigitos [1,4,6,9]   6  ==  2\n     numeroDeDigitos [1,4,6,9]  22  ==  3\n     numeroDeDigitos [4,6,9]    15  ==  3\n     numeroDeDigitos [6,9]      15  ==  4\n     numeroDeDigitos [1,4,6,9] (10^(10^5))  ==  166097\n     numeroDeDigitos   [4,6,9] (10^(10^5))  ==  209590\n     numeroDeDigitos     [6,9] (10^(10^5))  ==  332192\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericIndex, genericLength)\n\n-- Definici\u00f3n de numerosCon\n-- ========================\n\nnumerosCon :: [Integer] -> [Integer]\nnumerosCon xs = [n | n <- [0..]\n                   , n `tieneSusDigitosEn` xs]\n\n-- (tieneSusDigitosEn xs n) se verifica si los d\u00edgitos de n est\u00e1n contenidos en\n-- xs. Por ejemplo,\n--    4149 `tieneSusDigitosEn` [1,4,6,9]  ==  True\n--    4143 `tieneSusDigitosEn` [1,4,6,9]  ==  False\ntieneSusDigitosEn :: Integer -> [Integer] -> Bool\ntieneSusDigitosEn n xs =\n  digitos n `esSubconjunto` xs\n\n-- (digitos n) es la lista de los d\u00edgitos de n. Por ejemplo,\n--    digitos 325  ==  [3,2,5]\ndigitos :: Integer -> [Integer]\ndigitos n = [read [c] | c <- show n]\n\n-- (esSubconjunto xs ys) se verifica si xs es subconjunto de ys. Por\n-- ejemplo, \n--    esSubconjunto [3,2,5] [4,2,5,7,3]  ==  True\n--    esSubconjunto [3,2,5] [4,2,5,7]  ==  False\nesSubconjunto :: Eq a => [a] -> [a] -> Bool\nesSubconjunto xs ys = all (`elem` ys) xs\n\n-- 1\u00aa definici\u00f3n de numeroDeDigitos\n-- ================================\n\nnumeroDeDigitos :: [Integer] -> Integer -> Int\nnumeroDeDigitos xs n =\n  length (show (numerosCon xs `genericIndex` n))\n\n-- 2\u00aa definici\u00f3n de numeroDeDigitos\n-- ================================\n\n-- Observando que si el conjunto de d\u00edgitos tiene n elementos, entonces\n-- hay n^k n\u00fameros con k d\u00edgitos.\n\nnumeroDeDigitos2 :: [Integer] -> Integer -> Int\nnumeroDeDigitos2 xs n =\n  1 + length (takeWhile (<= n) (sumasDePotencias (genericLength xs)))\n\n-- (potencia n) son las potencias de n. Por ejemplo,\n--    take 5 (potencias 3)  ==  [3,9,27,81,243]\npotencias :: Integer -> [Integer]\npotencias k = iterate (*k) k \n\n-- (sumasDePotencias n) es la lista de las sumas acumuladas de las\n-- potencias de n. Por ejemplo,\n--    take 5 (sumasDePotencias 3)  ==  [3,12,39,120,363]\nsumasDePotencias :: Integer -> [Integer]\nsumasDePotencias k = scanl1 (+) (potencias k)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> numeroDeDigitos [1,4,6,9] 2000\n--    6\n--    (3.98 secs, 1,424,390,064 bytes)\n--    \u03bb> numeroDeDigitos2 [1,4,6,9] 2000\n--    6\n--    (0.01 secs, 127,464 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Definir las siguientes funciones numerosCon :: [Integer] -> [Integer] numeroDeDigitos :: [Integer] -> Integer -> Int tales que (numerosCon ds) es la lista de los n\u00fameros que se pueden construir con los d\u00edgitos de ds (cuyos elementos son distintos elementos del 1 al 9) . Por ejemplo, \u03bb> take 22 (numerosCon [1,4,6,9]) [1,4,6,9,11,14,16,19,41,44,46,49,61,64,66,69,91,94,96,99,111,114] \u03bb> take&#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":[5],"tags":[41,8,26,256,258,50,28,11,95,252,33,34],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4046"}],"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=4046"}],"version-history":[{"count":6,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4046\/revisions"}],"predecessor-version":[{"id":4078,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4046\/revisions\/4078"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4046"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4046"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4046"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}