{"id":2634,"date":"2016-11-30T06:00:35","date_gmt":"2016-11-30T04:00:35","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=2634"},"modified":"2016-12-07T06:38:24","modified_gmt":"2016-12-07T04:38:24","slug":"problema-de-las-particiones-optimas","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/problema-de-las-particiones-optimas\/","title":{"rendered":"Problema de las particiones \u00f3ptimas"},"content":{"rendered":"<p>El <strong>problema de la particiones \u00f3ptimas<\/strong> consiste en dada una lista xs dividirla en dos sublistas ys y zs tales que el valor absoluto de la diferencia de la suma de los elementos de xs y la suma de los elemento de zs sea lo menor posible.Cada una de estas divisiones (ys,zs) es una <strong>partici\u00f3n \u00f3ptima<\/strong> de xs. Por ejemplo, la partici\u00f3n \u00f3ptima de [2,3,5] es ([2,3],[5]) ya que |(2+3) &#8211; 5| = 0. Una lista puede tener distintas particiones \u00f3ptimas. Por ejemplo, [1,1,2,3] tiene dos particiones \u00f3ptimas ([1,2],[1,3]) y ([1,1,2],[3]) ambas con diferencia 1 (es decir, 1 = |(1+2)-(1+3)| = |(1+1+2)-3|).<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   particionesOptimas :: [Int] -> [([Int],[Int])]\n<\/pre>\n<p>tal que (particionesOptimas xs) es la lista de las particiones \u00f3ptimas de xs. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   particionesOptimas [2,3,5]    ==  [([2,3],[5])]\n   particionesOptimas [1,1,2,3]  ==  [([1,2],[1,3]),([1,1,2],[3])]\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List ((\\\\), nub, sort, subsequences)\n\n-- Una partici\u00f3n es un par de lista de enteros.\ntype Particion = ([Int],[Int])\n\n-- (particiones xs) es la lista de las particiones de xs. Por ejemplo,\n--    \u03bb> particiones [2,3,5]\n--    [([],[2,3,5]),([2],[3,5]),([2,3],[5]),([2,5],[3])]\nparticiones :: [Int] -> [Particion]\nparticiones xs =\n  [(sort ys, sort zs) | ys <- subsequences xs\n                      , let zs = xs \\\\ ys\n                      , ys <= zs]\n\n-- (diferencia p) es el valor absoluto de la diferencia de las sumas de\n-- los elementos de la partici\u00f3n p. Por ejemplo,\n--    diferencia ([2],[3,5])  ==  6\n--    diferencia ([2,3],[5])  ==  0\ndiferencia :: Particion -> Int\ndiferencia (xs,ys) = abs (sum xs - sum ys)\n\n-- (diferenciasParticiones xs) es la lista de las diferencias de las\n-- particiones de xs. Por ejemplo,\n--    diferenciasParticiones [2,3,5]  ==  [10,6,0,4]\ndiferenciasParticiones :: [Int] -> [Int]\ndiferenciasParticiones xs = map diferencia (particiones xs)\n\n-- (minDiferenciaParticiones xs) es el m\u00ednimo de las diferencias de las\n-- particiones de xs. Por ejemplo, \n--    minDiferenciaParticiones [2,3,5]    ==  0\n--    minDiferenciaParticiones [1,1,2,3]  ==  1\nminDiferenciaParticiones :: [Int] -> Int\nminDiferenciaParticiones = minimum . diferenciasParticiones\n\nparticionesOptimas :: [Int] -> [Particion]\nparticionesOptimas xs =\n  nub [(ys,zs) | (ys,zs) <- particiones xs\n               , diferencia (ys,zs) == m]\n  where m = minDiferenciaParticiones xs\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>El problema de la particiones \u00f3ptimas consiste en dada una lista xs dividirla en dos sublistas ys y zs tales que el valor absoluto de la diferencia de la suma de los elementos de xs y la suma de los elemento de zs sea lo menor posible.Cada una de estas divisiones (ys,zs) es una partici\u00f3n&#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":[8,10,340,24,11,14,88],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2634"}],"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=2634"}],"version-history":[{"count":6,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2634\/revisions"}],"predecessor-version":[{"id":2664,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/2634\/revisions\/2664"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=2634"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=2634"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=2634"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}