{"id":3342,"date":"2017-06-01T06:00:14","date_gmt":"2017-06-01T04:00:14","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=3342"},"modified":"2017-05-30T13:45:01","modified_gmt":"2017-05-30T11:45:01","slug":"mayores-sublistas-crecientes","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/mayores-sublistas-crecientes\/","title":{"rendered":"Mayores sublistas crecientes"},"content":{"rendered":"<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   mayoresCrecientes :: Ord a => [a] -> [[a]]\n   longitudMayorSublistaCreciente :: Ord a => [a] -> Int\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(mayoresCrecientes xs) es la lista de las sublistas crecientes de xs de mayor longitud. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> mayoresCrecientes [3,2,6,4,5,1]\n     [[3,4,5],[2,4,5]]\n     \u03bb> mayoresCrecientes [10,22,9,33,21,50,41,60,80]\n     [[10,22,33,50,60,80],[10,22,33,41,60,80]]\n     \u03bb> mayoresCrecientes [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]\n     [[0,4,6,9,13,15],[0,2,6,9,13,15],[0,4,6,9,11,15],[0,2,6,9,11,15]]\n     \u03bb> length (head (mayoresCrecientes (show (2^70))))\n     5\n<\/pre>\n<ul>\n<li>(longitudMayorSublistaCreciente xs) es el m\u00e1ximo de las longitudes de las sublistas crecientes de xs. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> longitudMayorSublistaCreciente [3,2,6,4,5,1]\n     3\n     \u03bb> longitudMayorSublistaCreciente [10,22,9,33,21,50,41,60,80]\n     6\n     \u03bb> longitudMayorSublistaCreciente [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]\n     6\n     \u03bb> longitudMayorSublistaCreciente [1..2000]\n     2000\n     \u03bb> longitudMayorSublistaCreciente [2000,1999..1]\n     1\n<\/pre>\n<h4>Soluciones<\/h4>\n<p>[schedule expon=&#8217;2017-06-08&#8242; expat=\u00bb06:00&#8243;]<\/p>\n<ul>\n<li>Las soluciones se pueden escribir en los comentarios hasta el 08 de junio.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=\u00bbhaskell\u00bb&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n<p>[\/schedule]<\/p>\n<p>[schedule on=&#8217;2017-06-08&#8242; at=\u00bb06:00&#8243;]<\/p>\n<pre lang=\"haskell\">\r\nimport Data.List (nub, sort, subsequences)\r\nimport Data.Array\r\n\r\n-- 1\u00aa definici\u00f3n de mayoresCrecientes\r\n-- ==================================\r\n\r\nmayoresCrecientes1 :: Ord a => [a] -> [[a]]\r\nmayoresCrecientes1 xs =\r\n  [ys | ys <- xss\r\n      , length ys == m]\r\n  where xss = sublistasCrecientes xs\r\n        m   = maximum (map length xss)\r\n\r\n-- (sublistasCrecientes1 xs) es la lista de las sublistas crecientes de\r\n-- xs. Por ejemplo,\r\n--    \u03bb> sublistasCrecientes [3,2,5]\r\n--    [[],[3],[2],[5],[3,5],[2,5]]\r\nsublistasCrecientes :: Ord a => [a] -> [[a]]\r\nsublistasCrecientes xs =\r\n  [ys | ys <- subsequences xs\r\n      , esCreciente ys]\r\n\r\n-- (esCreciente xs) se verifica si la lista xs es creciente. Por\r\n-- ejemplo,  \r\n--    esCreciente [2,3,5]  ==  True\r\n--    esCreciente [2,3,1]  ==  False\r\n--    esCreciente [2,3,3]  ==  False\r\nesCreciente :: Ord a => [a] -> Bool\r\nesCreciente (x:y:zs) = x < y &#038;&#038; esCreciente (y:zs)\r\nesCreciente _        = True\r\n\r\n-- 2\u00aa definici\u00f3n de mayoresCrecientes\r\n-- ==================================\r\n\r\nmayoresCrecientes2 :: Ord a => [a] -> [[a]]\r\nmayoresCrecientes2 xs =\r\n  [ys | ys <- xss\r\n      , length ys == m]\r\n  where xss = sublistasCrecientes2 xs\r\n        m   = maximum (map length xss)\r\n\r\n-- (sublistasCrecientes2 xs) es la lista de las sublistas crecientes de\r\n-- xs. Por ejemplo,\r\n--    \u03bb> sublistasCrecientes2 [3,2,5]\r\n--    [[3,5],[3],[2,5],[2],[5],[]]\r\nsublistasCrecientes2 :: Ord a => [a] -> [[a]]\r\nsublistasCrecientes2 []  = [[]]\r\nsublistasCrecientes2 (x:xs) =\r\n  [x:ys | ys <- yss, null ys || x < head ys] ++ yss\r\n  where yss = sublistasCrecientes2 xs\r\n\r\n-- Comparaci\u00f3n de eficiencia\r\n-- =========================\r\n\r\n--    \u03bb> length (head (mayoresCrecientes1 (show (2^70))))\r\n--    5\r\n--    (10.93 secs, 1,958,822,896 bytes)\r\n--    \u03bb> length (head (mayoresCrecientes2 (show (2^70))))\r\n--    5\r\n--    (0.02 secs, 0 bytes)\r\n\r\n-- 1\u00aa definici\u00f3n de longitudMayorSublistaCreciente\r\n-- ===============================================\r\n\r\nlongitudMayorSublistaCreciente1 :: Ord a => [a] -> Int\r\nlongitudMayorSublistaCreciente1 =\r\n  length . head . mayoresCrecientes1\r\n\r\n-- 2\u00aa definici\u00f3n de longitudMayorSublistaCreciente\r\n-- ===============================================\r\n\r\nlongitudMayorSublistaCreciente2 :: Ord a => [a] -> Int\r\nlongitudMayorSublistaCreciente2 =\r\n  length . head . mayoresCrecientes2\r\n\r\n-- Comparaci\u00f3n de eficiencia:\r\n--    \u03bb> longitudMayorSublistaCreciente1 (show (2^70))\r\n--    5\r\n--    (10.78 secs, 1,969,452,328 bytes)\r\n--    \u03bb> longitudMayorSublistaCreciente2 (show (2^70))\r\n--    5\r\n--    (0.02 secs, 0 bytes)\r\n\r\n-- 3\u00aa definici\u00f3n de longitudMayorSublistaCreciente\r\n-- ===============================================\r\n\r\nlongitudMayorSublistaCreciente3 :: Ord a => [a] -> Int\r\nlongitudMayorSublistaCreciente3 xs =\r\n  longitudSCM xs (sort (nub xs))\r\n  \r\n-- (longitudSCM xs ys) es la longitud de la subsecuencia m\u00e1xima de xs e\r\n-- ys. Por ejemplo, \r\n--   longitudSCM \"amapola\" \"matamoscas\" == 4\r\n--   longitudSCM \"atamos\" \"matamoscas\"  == 6\r\n--   longitudSCM \"aaa\" \"bbbb\"           == 0\r\nlongitudSCM :: Eq a => [a] -> [a] -> Int\r\nlongitudSCM xs ys = (matrizLongitudSCM xs ys) ! (n,m)\r\n  where n = length xs\r\n        m = length ys\r\n\r\n-- (matrizLongitudSCM2 xs ys) es la matriz de orden (n+1)x(m+1) (donde n\r\n-- y m son los n\u00fameros de elementos de xs e ys, respectivamente) tal que\r\n-- el valor en la posici\u00f3n (i,j) es la longitud de la SCM de los i\r\n-- primeros elementos de xs y los j primeros elementos de ys. Por ejemplo,\r\n--    \u03bb> elems (matrizLongitudSCM \"amapola\" \"matamoscas\")\r\n--    [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,2,2,2,2,2,2,\r\n--     0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,3,3,3,3,3,\r\n--     0,1,2,2,2,2,3,3,3,3,3,0,1,2,2,3,3,3,3,3,4,4]\r\n-- Gr\u00e1ficamente,\r\n--       m a t a m o s c a s\r\n--    [0,0,0,0,0,0,0,0,0,0,0,\r\n-- a   0,0,1,1,1,1,1,1,1,1,1,\r\n-- m   0,1,1,1,1,2,2,2,2,2,2,\r\n-- a   0,1,2,2,2,2,2,2,2,3,3,\r\n-- p   0,1,2,2,2,2,2,2,2,3,3,\r\n-- o   0,1,2,2,2,2,3,3,3,3,3,\r\n-- l   0,1,2,2,2,2,3,3,3,3,3,\r\n-- a   0,1,2,2,3,3,3,3,3,4,4]\r\nmatrizLongitudSCM :: Eq a => [a] -> [a] -> Array (Int,Int) Int\r\nmatrizLongitudSCM xs ys = q\r\n  where\r\n    n = length xs\r\n    m = length ys\r\n    v = listArray (1,n) xs\r\n    w = listArray (1,m) ys\r\n    q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]]\r\n      where f 0 _ = 0\r\n            f _ 0 = 0\r\n            f i j | v ! i == w ! j = 1 + q ! (i-1,j-1)\r\n                  | otherwise      = max (q ! (i-1,j)) (q ! (i,j-1))\r\n  \r\n-- Comparaci\u00f3n de eficiencia\r\n-- -------------------------\r\n\r\n--    \u03bb> longitudMayorSublistaCreciente2 [1..22]\r\n--    22\r\n--    (19.63 secs, 2,271,936,784 bytes)\r\n--    \u03bb> longitudMayorSublistaCreciente3 [1..22]\r\n--    22\r\n--    (0.01 secs, 0 bytes)\r\n\r\n-- 4\u00aa definici\u00f3n de longitudMayorSublistaCreciente\r\n-- ===============================================\r\n\r\nlongitudMayorSublistaCreciente4 :: Ord a => [a] -> Int\r\nlongitudMayorSublistaCreciente4 xs =\r\n  maximum (elems (vectorlongitudMayorSublistaCreciente xs))\r\n\r\n-- (vectorlongitudMayorSublistaCreciente xs) es el vector de longitud n\r\n-- tal que el valor i-\u00e9simo es la longitud de la sucesi\u00f3n m\u00e1s largar que\r\n-- termina en el elemento i-\u00e9simo de xs. Por ejemplo, \r\n--    \u03bb> vectorlongitudMayorSublistaCreciente [3,2,6,4,5,1]\r\n--    array (1,6) [(1,1),(2,1),(3,2),(4,2),(5,3),(6,1)]\r\nvectorlongitudMayorSublistaCreciente :: Ord a => [a] -> Array Int Int\r\nvectorlongitudMayorSublistaCreciente xs = v\r\n  where v = array (1,n) [(i,f i) | i <- [1..n]]\r\n        n = length xs\r\n        w = listArray (1,n) xs\r\n        f 1 = 1\r\n        f i | null ls   = 1\r\n            | otherwise = 1 + maximum ls\r\n          where ls = [v ! j | j <- [1..i-1], w ! j < w ! i]\r\n<\/pre>\n<p>[\/schedule]<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Definir las funciones mayoresCrecientes :: Ord a => [a] -> [[a]] longitudMayorSublistaCreciente :: Ord a => [a] -> Int tales que (mayoresCrecientes xs) es la lista de las sublistas crecientes de xs de mayor longitud. Por ejemplo, \u03bb> mayoresCrecientes [3,2,6,4,5,1] [[3,4,5],[2,4,5]] \u03bb> mayoresCrecientes [10,22,9,33,21,50,41,60,80] [[10,22,33,50,60,80],[10,22,33,41,60,80]] \u03bb> mayoresCrecientes [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15] [[0,4,6,9,13,15],[0,2,6,9,13,15],[0,4,6,9,11,15],[0,2,6,9,11,15]] \u03bb> length (head (mayoresCrecientes (show (2^70))))&#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":[2],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3342"}],"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=3342"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3342\/revisions"}],"predecessor-version":[{"id":3343,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3342\/revisions\/3343"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3342"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3342"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3342"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}