{"id":2169,"date":"2016-02-26T06:00:26","date_gmt":"2016-02-26T04:00:26","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2169"},"modified":"2016-05-01T20:04:02","modified_gmt":"2016-05-01T18:04:02","slug":"particiones-en-sumas-de-cuadrados","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/particiones-en-sumas-de-cuadrados\/","title":{"rendered":"Particiones en sumas de cuadrados"},"content":{"rendered":"<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   particionesCuadradas        :: Integer -> [[Integer]]\n   nParticionesCuadradas       :: Integer -> Integer\n   graficaParticionesCuadradas :: Integer -> IO ()\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(particionesCuadradas n) es la listas de conjuntos de cuadrados cuya suma es n. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n      particionesCuadradas 3  ==  [[1,1,1]]\n      particionesCuadradas 4  ==  [[4],[1,1,1,1]]\n      particionesCuadradas 9  ==  [[9],[4,4,1],[4,1,1,1,1,1],[1,1,1,1,1,1,1,1,1]]\n<\/pre>\n<ul>\n<li>(nParticionesCuadradas n) es el n\u00famero de conjuntos de cuadrados cuya suma es n. Por ejemplo, <\/li>\n<\/ul>\n<pre lang=\"text\">\n      nParticionesCuadradas 3    ==  1\n      nParticionesCuadradas 4    ==  2\n      nParticionesCuadradas 9    ==  4\n      nParticionesCuadradas 50   ==  104\n      nParticionesCuadradas 100  ==  1116\n      nParticionesCuadradas 200  ==  27482\n<\/pre>\n<ul>\n<li>(graficaParticionesCuadradas n) dibuja la gr\u00e1fica de la sucesi\u00f3n<\/li>\n<\/ul>\n<pre lang=\"text\">\n      [nParticionesCuadradas k | k <- [0..n]]\n<\/pre>\n<p>Por ejemplo, con (graficaParticionesCuadradas 100) se obtiene<\/p>\n<p><a href=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2016\/02\/Particiones_en_sumas_de_cuadrados.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2016\/02\/Particiones_en_sumas_de_cuadrados.png?resize=624%2C376\" alt=\"Particiones_en_sumas_de_cuadrados\" width=\"624\" height=\"376\" class=\"aligncenter size-full wp-image-2173\" srcset=\"https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2016\/02\/Particiones_en_sumas_de_cuadrados.png?w=624&amp;ssl=1 624w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2016\/02\/Particiones_en_sumas_de_cuadrados.png?resize=300%2C180&amp;ssl=1 300w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2016\/02\/Particiones_en_sumas_de_cuadrados.png?resize=100%2C60&amp;ssl=1 100w, https:\/\/i0.wp.com\/www.glc.us.es\/~jalonso\/exercitium\/wp-content\/uploads\/2016\/02\/Particiones_en_sumas_de_cuadrados.png?resize=150%2C90&amp;ssl=1 150w\" sizes=\"(max-width: 624px) 100vw, 624px\" data-recalc-dims=\"1\" \/><\/a><\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericLength)\nimport Graphics.Gnuplot.Simple\n\n-- Definici\u00f3n de particiones cuadradas\n-- ===================================\n\nparticionesCuadradas :: Integer -> [[Integer]]\nparticionesCuadradas n = \n    particiones n (reverse $ takeWhile (<=n) cuadrados)\n\n-- cuadrados es la lista de los cuadrados. Por ejemplo,\n--    take 12 cuadrados  ==  [1,4,9,16,25,36,49,64,81,100,121,144]\ncuadrados :: [Integer]\ncuadrados = map (^2) [1..]\n\n-- (particiones n xs) es la lista de las particiones de n como suma de\n-- elementos de xs, donde xs es una lista no creciente. Por ejemplo,\n--    particiones 10 [7,4,2]  ==  [[4,4,2],[4,2,2,2],[2,2,2,2,2]]\n--    particiones 11 [7,4,2]  ==  [[7,4],[7,2,2]]\n--    particiones  5 [7,4,2]  ==  []\nparticiones:: Integer -> [Integer] -> [[Integer]]\nparticiones _ [] = []\nparticiones n (x:xs)\n    | x >  n    = particiones n xs\n    | x == n    = [n] : particiones n xs\n    | otherwise = map (x:) (particiones (n-x) (x:xs)) ++ particiones n xs\n\n-- 1\u00aa definici\u00f3n de nParticionesCuadradas       \nnParticionesCuadradas1 :: Integer -> Integer\nnParticionesCuadradas1 = genericLength . particionesCuadradas\n\n-- 2\u00aa definici\u00f3n nParticionesCuadradas   \nnParticionesCuadradas2 :: Integer -> Integer\nnParticionesCuadradas2 n = aux n (reverse $ takeWhile (<=n) cuadrados) where\n    aux _ [] = 0\n    aux n ys@(x:xs) | x >  n    = aux n xs\n                    | x == n    = 1 + aux n xs\n                    | otherwise = aux (n-x) ys + aux n xs\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> nParticionesCuadradas1 250\n--    94987\n--    (4.21 secs, 3,256,031,528 bytes)\n--    \u03bb> nParticionesCuadradas2 250\n--    94987\n--    (2.93 secs, 1,714,701,504 bytes)\n\n-- Definici\u00f3n de graficaParticionesCuadradas\n-- =========================================\n                                  \ngraficaParticionesCuadradas :: Integer  -> IO ()\ngraficaParticionesCuadradas n = \n    plotList [Key Nothing] [nParticionesCuadradas2 k | k <- [0..n]]\n<\/pre>\n<h4>Referencias<\/h4>\n<ul>\n<li><a href=\"http:\/\/oeis.org\/A001156\">Sucesi\u00f3n A001156<\/a> de OEIS.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Definir las funciones particionesCuadradas :: Integer -> [[Integer]] nParticionesCuadradas :: Integer -> Integer graficaParticionesCuadradas :: Integer -> IO () tales que (particionesCuadradas n) es la listas de conjuntos de cuadrados cuya suma es n. Por ejemplo, particionesCuadradas 3 == [[1,1,1]] particionesCuadradas 4 == [[4],[1,1,1,1]] particionesCuadradas 9 == [[9],[4,4,1],[4,1,1,1,1,1],[1,1,1,1,1,1,1,1,1]] (nParticionesCuadradas n) es el n\u00famero de conjuntos&#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":[258,10,11,6,32,34],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2169"}],"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=2169"}],"version-history":[{"count":8,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2169\/revisions"}],"predecessor-version":[{"id":2200,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2169\/revisions\/2200"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2169"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2169"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2169"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}