{"id":2068,"date":"2012-05-31T18:10:18","date_gmt":"2012-05-31T18:10:18","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=2068"},"modified":"2013-03-08T05:48:14","modified_gmt":"2013-03-08T05:48:14","slug":"biparticiones-con-igual-suma-que-producto-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/biparticiones-con-igual-suma-que-producto-en-haskell\/","title":{"rendered":"Biparticiones con igual suma que producto en Haskell"},"content":{"rendered":"<p>En <a href=\"http:\/\/simplementenumeros.blogspot.com.es\/2012\/05\/936-dividiendo-los-numeros.html\"> N\u00fameros y algo m\u00e1s &#8230;<\/a> se ha planteado el siguiente problema<\/p>\n<blockquote><p>\n\u00bfEs posible dividir todos los n\u00fameros del 1 al 2012 en dos grupos, S y P, tal que la suma de los n\u00fameros de S sea igual al producto de los n\u00fameros que est\u00e1n en P? \u00bfy si fueran 2011 \u00f3 2013? Si es posible, \u00bfC\u00f3mo estar\u00edan formados esos conjuntos?\n<\/p><\/blockquote>\n<p>En la siguiente relaci\u00f3n de ejercicios (elaborada para la asignatura de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a>) se resuelve el problema con Haskell.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Librer\u00edas auxiliares                                             --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Data.List\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Ejercicios                                                       --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n\r\n--    particiones :: Integer -> [([Integer],[Integer])]\r\n-- tal que (particiones n) es una lista de pares de listas (xs,ys) tales\r\n-- que xs, ys es una partici\u00f3n de los n primeros n\u00fameros naturales y la\r\n-- suma de los elementos xs es igual que el producto de los elementos de\r\n-- ys. Por ejemplo,\r\n--    ghci> particiones 10\r\n--    [([9,8,7,6,5,3,2],[1,4,10]),\r\n--     ([10,9,8,5,4,3,2,1],[6,7]),\r\n--     ([10,9,8,6,5,4],[1,2,3,7])]\r\n-- Obs\u00e9rvese que las particiones est\u00e1n ordenadas lexicogr\u00e1ficamente en\r\n-- sus primeras componentes.\r\n-- ---------------------------------------------------------------------\r\n \r\nparticiones :: Integer -> [([Integer],[Integer])]\r\nparticiones 1 = []\r\nparticiones n = aux [n,n-1..1] [] (sum [1..n]) 1 where\r\n    aux xs ys s p \r\n        | s == p      = [(xs,ys)]\r\n        | s < p       = []\r\n        | otherwise   = concat [aux (delete x xs) (x:ys) (s-x) (p*x)\r\n                                | x <- xs, \r\n                                  null ys || x < head ys,\r\n                                  s-x >= p*x]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Calcular las primeras de las (particiones n) para n\r\n-- entre 5 y 12. \r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es \r\n--    ghci> head (particiones 5)\r\n--    ([5,3],[1,2,4])\r\n--    ghci> head (particiones 6)\r\n--    ([5,4,3],[1,2,6])\r\n--    ghci> head (particiones 7)\r\n--    ([7,5,4,2],[1,3,6])\r\n--    ghci> head (particiones 8)\r\n--    ([7,6,5,4,2],[1,3,8])\r\n--    ghci> head (particiones 9)\r\n--    ([9,7,6,5,3,2],[1,4,8])\r\n--    ghci> head (particiones 10)\r\n--    ([9,8,7,6,5,3,2],[1,4,10])\r\n--    ghci> head (particiones 11)\r\n--    ([11,9,8,7,6,4,3,2],[1,5,10])\r\n--    ghci> head (particiones 12)\r\n--    ([11,10,9,8,7,6,4,3,2],[1,5,12])\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. A la vista de los resultados del ejercicios anterior,\r\n-- conjeturar una f\u00f3rmula para calcular la primera de las particiones.\r\n-- Indicaci\u00f3n: Fijarse en la segunda componente distiguiendo casos seg\u00fan\r\n-- la paridad de n.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Para n par las segundas componentes de las particiones son\r\n--       n | \r\n--      ---+----------\r\n--       6 | [1,2,6]\r\n--       8 | [1,3,8]\r\n--      10 | [1,4,10]\r\n--      12 | [1,5,12]\r\n-- La conjetura es que es una terna cuyos elementos son 1, n\/2-1 y n. \r\n-- \r\n-- Para n impar las segundas componentes de las particiones son\r\n--       n | \r\n--      ---+----------\r\n--       5 | [1,2,4]\r\n--       7 | [1,3,6]\r\n--       9 | [1,4,8]\r\n--      11 | [1,5,10]\r\n-- La conjetura es que es una terna cuyos elementos son 1, (n-1)\/2 y\r\n-- n-1.  \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir la funci\u00f3n\r\n--    particion :: Integer -> ([Integer],[Integer])\r\n-- donde (particion n) es la partici\u00f3n de n calculada usando la\r\n-- conjetura del ejercicio anterior.\r\n-- ---------------------------------------------------------------------\r\n\r\nparticion :: Integer -> ([Integer],[Integer])\r\nparticion n | even n    = ([n,n-1..1] \\\\ pPar,   pPar)\r\n            | otherwise = ([n,n-1..1] \\\\ pImpar, pImpar)\r\n            where pPar   = [1, n `div` 2 - 1, n]\r\n                  pImpar = [1, (n-1) `div` 2, n-1]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Comprobar con QuickCheck que, para n >= 5, si el valor\r\n-- de (particion n) es (xs,ys), entonces la suma de los elementos de xs\r\n-- es igual que el producto de los elementos de ys.\r\n-- --------------------------------------------------------------------- \r\n\r\n-- La propiedad es\r\nprop_particion :: Integer -> Property\r\nprop_particion n =\r\n    n >= 5 ==> n*(n+1) `div` 2 - sum ys == product ys\r\n    where (xs,ys) = particion n\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_particion\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Demostrar que, para n >= 5, si el valor de (particion n)\r\n-- es (xs,ys), entonces la suma de los elementos de xs es igual que el\r\n-- producto de los elementos de ys. \r\n-- --------------------------------------------------------------------- \r\n\r\n-- Para n = 2m, se tiene que\r\n--   sum xs     = sum [1..2m] - sum [1,m-1,2m]\r\n--              = 2m(2m+1)\/2 - (1+m-1+2m) \r\n--              = 2m^2 + m - 3m\r\n--              = 2m^2 - 2m\r\n--   product ys = 1*(m-1)*2m\r\n--              = 2m^2 - 2m\r\n-- \r\n-- Para n = 2m+1, se tiene que\r\n--   sum xs     = sum [1..2m+1] - sum [1,m,2m]\r\n--              = (2m+1)(2m+2)\/2 - (1+m+2m) \r\n--              = 2m^2 + 3m + 1 - 1 - 3m\r\n--              = 2m^2 \r\n--   product ys = 1*m*2m\r\n--              = 2m^2\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Resolver el problema inicial; es decir calcular una\r\n-- partici\u00f3n de los n\u00fameros 2011, 2012 y 2013.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo de los segundos elementos de las particiones (los primeros\r\n-- son los restantes) es\r\n--    ghci> snd (particion 2011)\r\n--    [1,1005,2010]\r\n--    ghci> snd (particion 2012)\r\n--    [1,1005,2012]\r\n--    ghci> snd (particion 2013)\r\n--    [1,1006,2012]\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En N\u00fameros y algo m\u00e1s &#8230; se ha planteado el siguiente problema \u00bfEs posible dividir todos los n\u00fameros del 1 al 2012 en dos grupos, S y P, tal que la suma de los n\u00fameros de S sea igual al producto de los n\u00fameros que est\u00e1n en P? \u00bfy si fueran 2011 \u00f3 2013? Si&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","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":[270,126],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2068"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=2068"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2068\/revisions"}],"predecessor-version":[{"id":2812,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2068\/revisions\/2812"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=2068"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=2068"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=2068"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}