{"id":3494,"date":"2017-12-08T06:00:04","date_gmt":"2017-12-08T04:00:04","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=3494"},"modified":"2017-12-15T07:33:37","modified_gmt":"2017-12-15T05:33:37","slug":"ordenacion-valle","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/ordenacion-valle\/","title":{"rendered":"Ordenaci\u00f3n valle"},"content":{"rendered":"<p>La ordenaci\u00f3n valle de la lista [79,35,54,19,35,25,12] es la lista [79,35,25,12,19,35,54] ya que es una permutaci\u00f3n de la primera y cumple las siguientes condiciones<\/p>\n<ul>\n<li>se compone de una parte decreciente ([79,35,25]), un elemento m\u00ednimo (12) y una parte creciente ([19,35,54]);<\/li>\n<li>las dos partes tienen el mismo n\u00famero de elementos;<\/li>\n<li>cada elemento de la primera parte es mayor o igual que su correspondiente en la segunda parte; es decir. 79 \u2265 54, 35 \u2265 35 y 25 \u2265 19;<\/li>\n<li>adem\u00e1s, la diferencia entre dichos elementos es la menor posible.<\/li>\n<\/ul>\n<p>En el caso, de que la longitud de la lista sea par, la divisi\u00f3n tiene s\u00f3lo dos partes (sin diferenciar el menor elemento). Por ejemplo, el valle de [79,35,54,19,35,25] es [79,35,25,19,35,54].<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   valle :: [Int] -> [Int]\n<\/pre>\n<p>tal que (valle xs) es la ordenaci\u00f3n valle de la lista xs. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   valle [79,35,54,19,35,25,12]       ==  [79,35,25,12,19,35,54]\n   valle [79,35,54,19,35,25]          ==  [79,35,25,19,35,54]\n   valle [67,93,100,-16,65,97,92]     ==  [100,93,67,-16,65,92,97]\n   valle [14,14,14,14,7,14]           ==  [14,14,14,7,14,14]\n   valle [14,14,14,14,14]             ==  [14,14,14,14,14]\n   valle [17,17,15,14,8,7,7,5,4,4,1]  ==  [17,15,8,7,4,1,4,5,7,14,17]\n<\/pre>\n<p>En el \u00faltimo ejemplo se muestra c\u00f3mo la \u00faltima condici\u00f3n descarta la posibilidad de que la lista [17,17,15,14,8,1,4,4,5,7,7] tambi\u00e9n sea soluci\u00f3n ya que aunque se cumplen se cumplen las tres primeras condiciones la diferencia entre los elementos correspondientes es mayor que en la soluci\u00f3n; por ejemplo, 17 &#8211; 7 > 17 &#8211; 17.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (sort, sortBy)\n\n-- 1\u00aa soluci\u00f3n\nvalle1 :: [Int] -> [Int]\nvalle1 xs = ys ++ reverse zs\n  where (ys,zs) = aux (reverse (sort xs))\n        aux []       = ([],[])\n        aux [x]      = ([x],[])\n        aux [x,y]    = ([x,y],[])\n        aux (x:y:zs) = (x:as,y:bs)\n          where (as,bs) = aux zs\n\n-- 2\u00aa soluci\u00f3n\nvalle2 :: [Int] -> [Int]\nvalle2 = aux . reverse . sort\n  where aux []       = []\n        aux [x]      = [x]\n        aux (x:y:xs) = x : aux xs ++ [y]\n\n-- 3\u00aa soluci\u00f3n\nvalle3 :: [Int] -> [Int]\nvalle3 = aux . sortBy (flip compare)\n  where aux []       = []\n        aux [x]      = [x]\n        aux (x:y:xs) = x : aux xs ++ [y]\n        \n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- \u03bb> length (valle1 [1..2*10^4])\n-- 20000\n-- (0.02 secs, 8,621,240 bytes)\n-- \u03bb> length (valle2 [1..2*10^4])\n-- 20000\n-- (2.68 secs, 8,595,637,880 bytes)\n-- \u03bb> length (valle3 [1..2*10^4])\n-- 20000\n-- (2.67 secs, 8,594,678,104 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>La ordenaci\u00f3n valle de la lista [79,35,54,19,35,25,12] es la lista [79,35,25,12,19,35,54] ya que es una permutaci\u00f3n de la primera y cumple las siguientes condiciones se compone de una parte decreciente ([79,35,25]), un elemento m\u00ednimo (12) y una parte creciente ([19,35,54]); las dos partes tienen el mismo n\u00famero de elementos; cada elemento de la primera parte&#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":[161,160,11,6,32,14,159],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3494"}],"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=3494"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3494\/revisions"}],"predecessor-version":[{"id":3533,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3494\/revisions\/3533"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3494"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3494"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3494"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}