{"id":3924,"date":"2018-03-30T09:13:28","date_gmt":"2018-03-30T07:13:28","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=3924"},"modified":"2018-04-07T08:35:07","modified_gmt":"2018-04-07T06:35:07","slug":"arbol-de-subconjuntos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/arbol-de-subconjuntos\/","title":{"rendered":"\u00c1rbol de subconjuntos"},"content":{"rendered":"<p>Definir las siguientes funciones<\/p>\n<pre lang=\"text\">\n   arbolSubconjuntos       :: [a] -> Tree [a]\n   nNodosArbolSubconjuntos :: Integer -> Integer\n   sumaNNodos              :: Integer -> Integer\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(arbolSubconjuntos xs) es el \u00e1rbol de los subconjuntos de xs. Por ejemplo. <\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> putStrLn (drawTree (arbolSubconjuntos \"abc\"))\n     abc\n     |\n     +- bc\n     |  |\n     |  +- c\n     |  |\n     |  `- b\n     |\n     +- ac\n     |  |\n     |  +- c\n     |  |\n     |  `- a\n     |\n     `- ab\n        |\n        +- b\n        |\n        `- a\n<\/pre>\n<ul>\n<li>(nNodosArbolSubconjuntos xs) es el n\u00famero de nodos del \u00e1rbol de xs. Por ejemplo <\/li>\n<\/ul>\n<pre lang=\"text\">\n     nNodosArbolSubconjuntos \"abc\"  ==  10\n     nNodosArbolSubconjuntos [1..4*10^4] `mod` (7+10^9) == 546503960\n<\/pre>\n<ul>\n<li>(sumaNNodos n) es la suma del n\u00famero de nodos de los \u00e1rboles de los subconjuntos de [1..k] para 1 &lt;= k &lt;= n. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> sumaNNodos 3  ==  14\n     sumaNNodos (4*10^4) `mod` (7+10^9)  ==  249479844\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericLength, genericTake)\nimport Data.Tree (Tree (Node))\n\n-- Definici\u00f3n de arbolSubconjuntos\n-- ===============================\n\narbolSubconjuntos :: [a] -> Tree [a]\narbolSubconjuntos [x] = Node [x] []\narbolSubconjuntos xs =\n  Node xs (map arbolSubconjuntos (sinUno xs))\n\n-- (sinUno xs) es la lista obtenidas eliminando un elemento de xs. Por\n-- ejemplo, \n--    sinUno \"abcde\"  ==  [\"bcde\",\"acde\",\"abde\",\"abce\",\"abcd\"]\nsinUno :: [a] -> [[a]]\nsinUno xs =\n  [ys ++ zs | n <- [0..length xs - 1]\n            , let (ys,_:zs) = splitAt n xs]       \n\n-- 1\u00aa definici\u00f3n de nNodosArbolSubconjuntos\n-- ========================================\n\nnNodosArbolSubconjuntos :: [a] -> Integer\nnNodosArbolSubconjuntos =\n  fromIntegral . length . arbolSubconjuntos \n\n-- 2\u00aa definici\u00f3n de nNodosArbolSubconjuntos\n-- ========================================\n\nnNodosArbolSubconjuntos2 :: [a] -> Integer\nnNodosArbolSubconjuntos2 = aux . genericLength\n  where aux 1 = 1\n        aux n = 1 + n * aux (n-1)\n\n-- 3\u00aa definici\u00f3n de nNodosArbolSubconjuntos\n-- ========================================\n\nnNodosArbolSubconjuntos3 :: [a] -> Integer\nnNodosArbolSubconjuntos3 xs =\n  sucNNodos !! (n-1)\n  where n = length xs\n\n-- sucNNodos es la sucesi\u00f3n de los n\u00fameros de nodos de los \u00e1rboles de\n-- los subconjuntos con 1, 2, ... elementos. Por ejemplo.\n--    \u03bb> take 10 sucNNodos\n--    [1,3,10,41,206,1237,8660,69281,623530,6235301]\nsucNNodos :: [Integer]\nsucNNodos =\n  1 : map (+ 1) (zipWith (*) [2..] sucNNodos)\n\n-- Comparaci\u00f3n de eficiencia de nNodosArbolSubconjuntos\n-- ====================================================\n\n--    \u03bb> nNodosArbolSubconjuntos 10\n--    6235301\n--    (9.66 secs, 5,491,704,944 bytes)\n--    \u03bb> nNodosArbolSubconjuntos2 10\n--    6235301\n--    (0.00 secs, 145,976 bytes)\n--\n--    \u03bb> length (show (nNodosArbolSubconjuntos2 (4*10^4)))\n--    166714\n--    (1.07 secs, 2,952,675,472 bytes)\n--    \u03bb> length (show (nNodosArbolSubconjuntos3 (4*10^4)))\n--    166714\n--    (1.53 secs, 2,959,020,680 bytes)\n\n-- 1\u00aa definici\u00f3n de sumaNNodos\n-- ===========================\n\nsumaNNodos :: Integer -> Integer\nsumaNNodos n =\n  sum [nNodosArbolSubconjuntos [1..k] | k <- [1..n]]\n\n-- 2\u00aa definici\u00f3n de sumaNNodos\n-- ===========================\n\nsumaNNodos2 :: Integer -> Integer\nsumaNNodos2 n =\n  sum [nNodosArbolSubconjuntos2 [1..k] | k <- [1..n]]\n\n-- 3\u00aa definici\u00f3n de sumaNNodos\n-- ===========================\n\nsumaNNodos3 :: Integer -> Integer\nsumaNNodos3 n =\n  sum (genericTake n sucNNodos)\n\n-- Comparaci\u00f3n de eficiencia de sumaNNodos\n-- =======================================\n\n--    \u03bb> sumaNNodos 10 `mod` (7+10^9)\n--    6938270\n--    (16.00 secs, 9,552,410,688 bytes)\n--    \u03bb> sumaNNodos2 10 `mod` (7+10^9)\n--    6938270\n--    (0.00 secs, 177,632 bytes)\n-- \n--    \u03bb> sumaNNodos2 (2*10^3) `mod` (7+10^9)\n--    851467820\n--    (2.62 secs, 4,622,117,976 bytes)\n--    \u03bb> sumaNNodos3 (2*10^3) `mod` (7+10^9)\n--    851467820\n--    (0.01 secs, 8,645,336 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Definir las siguientes funciones arbolSubconjuntos :: [a] -> Tree [a] nNodosArbolSubconjuntos :: Integer -> Integer sumaNNodos :: Integer -> Integer tales que (arbolSubconjuntos xs) es el \u00e1rbol de los subconjuntos de xs. Por ejemplo. \u03bb> putStrLn (drawTree (arbolSubconjuntos \u00ababc\u00bb)) abc | +- bc | | | +- c | | | `- b | +-&#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":[2],"tags":[269,8,444,183,258,306,28,10,11,312,6,73,40,76],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3924"}],"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=3924"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3924\/revisions"}],"predecessor-version":[{"id":3948,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3924\/revisions\/3948"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3924"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3924"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3924"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}