{"id":2461,"date":"2016-05-19T06:00:29","date_gmt":"2016-05-19T04:00:29","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2461"},"modified":"2016-05-26T09:28:57","modified_gmt":"2016-05-26T07:28:57","slug":"particiones-de-longitud-fija","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/particiones-de-longitud-fija\/","title":{"rendered":"Particiones de longitud fija"},"content":{"rendered":"<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   particionesFijas :: Int -> Int -> [[Int]]\n<\/pre>\n<p>tal que (particionesFijas n k) es la lista de listas de k n\u00fameros naturales no crecientes cuya suma es n. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   ghci> particionesFijas 8 2\n   [[4,4],[5,3],[6,2],[7,1]]\n   ghci> particionesFijas 8 3\n   [[3,3,2],[4,2,2],[4,3,1],[5,2,1],[6,1,1]]\n   ghci> particionesFijas 9 3\n   [[3,3,3],[4,3,2],[4,4,1],[5,2,2],[5,3,1],[6,2,1],[7,1,1]]\n   ghci> length (particionesFijas 67 5)\n   8056\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\n-- 1\u00aa definici\u00f3n\nparticionesFijas :: Int -> Int -> [[Int]]\nparticionesFijas n 1 = [[n]]\nparticionesFijas n k \n    | k < 1     = []\n    | otherwise = [x:y:ys | x <- [1..n-1], \n                            (y:ys) <- particionesFijas (n-x) (k-1),\n                            x >= y]\n\n-- 2\u00aa definici\u00f3n\nparticionesFijas2 :: Int -> Int -> [[Int]]\nparticionesFijas2 n k\n    | k <= 0    = []\n    | k == 1    = [[n]]\n    | k == n    = [replicate k 1]\n    | k > n     = []\n    | otherwise = [xs ++ [1] | xs <- particionesFijas2 (n-1) (k-1)] ++\n                  [[x+1 | x <- xs] | xs <- particionesFijas2 (n-k) k]\n\n-- Comparaci\u00f3n:\n--    ghci> length (particionesFijas 800 3)\n--    53333\n--    (1.01 secs, 97696476 bytes)\n--    \n--    ghci> length (particionesFijas2 800 3)\n--    53333\n--    (4.52 secs, 693969028 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Definir la funci\u00f3n particionesFijas :: Int -> Int -> [[Int]] tal que (particionesFijas n k) es la lista de listas de k n\u00fameros naturales no crecientes cuya suma es n. Por ejemplo, ghci> particionesFijas 8 2 [[4,4],[5,3],[6,2],[7,1]] ghci> particionesFijas 8 3 [[3,3,2],[4,2,2],[4,3,1],[5,2,1],[6,1,1]] ghci> particionesFijas 9 3 [[3,3,3],[4,3,2],[4,4,1],[5,2,2],[5,3,1],[6,2,1],[7,1,1]] ghci> length (particionesFijas 67 5) 8056 Soluciones &#8211;&#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":[7],"tags":[6,19,14],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2461"}],"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=2461"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2461\/revisions"}],"predecessor-version":[{"id":2496,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2461\/revisions\/2496"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2461"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2461"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2461"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}