{"id":3576,"date":"2018-01-02T06:00:21","date_gmt":"2018-01-02T04:00:21","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=3576"},"modified":"2018-02-19T08:34:59","modified_gmt":"2018-02-19T06:34:59","slug":"el-problema-3sum","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/el-problema-3sum\/","title":{"rendered":"El problema 3SUM"},"content":{"rendered":"<p>El problem 3SUM consiste en dado una lista xs, decidir si xs posee tres elementos cuya suma sea cero. Por ejemplo, en [7,5,-9,5,2] se pueden elegir los elementos 7, -9 y 2 que suman 0.<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   sols3Sum :: [Int] -> [[Int]]\n   pb3Sum :: [Int] -> Bool\n<\/pre>\n<p>tales que<br \/>\n+ (sols3Sum xs) son las listas de tres elementos de xs cuya suma sea cero. Por ejemplo,<\/p>\n<pre lang=\"text\">\n      sols3Sum [8,10,-10,-7,2,-3]   ==  [[-10,2,8],[-7,-3,10]]\n      sols3Sum [-2..3]              ==  [[-2,-1,3],[-2,0,2],[-1,0,1]]\n      sols3Sum [1,-2]               ==  []\n      sols3Sum [-2,1]               ==  []\n      sols3Sum [1,-2,1]             ==  [[-2,1,1]]\n      length (sols3Sum [-100..100]) ==  5000\n<\/pre>\n<ul>\n<li>(pb3Sum xs) se verifica si xs posee tres elementos cuya suma sea cero. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     pb3Sum [8,10,-10,-7,2,-3]  ==  True\n     pb3Sum [1,-2]              ==  False\n     pb3Sum [-2,1]              ==  False\n     pb3Sum [1,-2,1]            ==  True\n     pb3Sum [1..400]            ==  False\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nsols3Sum1 :: [Int] -> [[Int]]\nsols3Sum1 = normaliza . sols3Sum1Aux \n\nsols3Sum1Aux :: [Int] -> [[Int]]\nsols3Sum1Aux xs =\n  [ys | ys <- subsequences xs\n      , length ys == 3\n      , sum ys == 0]\n\nnormaliza :: [[Int]] -> [[Int]]\nnormaliza = sort . nub . map sort\n\npb3Sum1 :: [Int] -> Bool\npb3Sum1 = not . null . sols3Sum1Aux\n\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nsols3Sum2 :: [Int] -> [[Int]]\nsols3Sum2 = normaliza . sols3Sum2Aux \n\nsols3Sum2Aux :: [Int] -> [[Int]]\nsols3Sum2Aux xs =\n  [[a,b,c] | (a:bs) <- tails xs\n           , (b:cs) <- tails bs\n           , c <- cs\n           , a + b + c == 0]\n  \npb3Sum2 :: [Int] -> Bool\npb3Sum2 = not . null . sols3Sum2Aux\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nsols3Sum3 :: [Int] -> [[Int]]\nsols3Sum3 = normaliza . sols3Sum3Aux \n\nsols3Sum3Aux :: [Int] -> [[Int]]\nsols3Sum3Aux xs =\n  [[a,b,-a-b] | (a:bs) <- tails xs\n              , b <- bs\n              , (-a-b) `elem` (delete a (delete b xs))]\n\npb3Sum3 :: [Int] -> Bool\npb3Sum3 = not . null . sols3Sum3Aux\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> pb3Suma [1..23]\n--    False\n--    (2.61 secs, 1,812,734,176 bytes)\n--    \u03bb> pb3Sumb [1..23]\n--    False\n--    (0.01 secs, 554,496 bytes)\n--    \u03bb> pb3Sumc [1..23]\n--    False\n--    (0.01 secs, 584,344 bytes)\n--    \u03bb> pb3Suma ([1..23] ++ [-3]) \n--    True\n--    (2.54 secs, 1,812,735,784 bytes)\n--    \u03bb> pb3Sumb ([1..23] ++ [-3]) \n--    True\n--    (0.01 secs, 148,904 bytes)\n--    \u03bb> pb3Sumc ([1..23] ++ [-3]) \n--    True\n--    (0.00 secs, 145,320 bytes)\n--\n--    \u03bb> pb3Sumb [1..300]\n--    False\n--    (1.66 secs, 933,699,824 bytes)\n--    \u03bb> pb3Sumc [1..300]\n--    False\n--    (0.41 secs, 873,168,120 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>El problem 3SUM consiste en dado una lista xs, decidir si xs posee tres elementos cuya suma sea cero. Por ejemplo, en [7,5,-9,5,2] se pueden elegir los elementos 7, -9 y 2 que suman 0. Definir las funciones sols3Sum :: [Int] -> [[Int]] pb3Sum :: [Int] -> Bool tales que + (sols3Sum xs) son las&#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":[4],"tags":[8,25,28,10,181,24,141,11,14,88,40,75],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3576"}],"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=3576"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3576\/revisions"}],"predecessor-version":[{"id":3790,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3576\/revisions\/3790"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3576"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3576"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3576"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}