{"id":8227,"date":"2023-06-26T06:00:01","date_gmt":"2023-06-26T04:00:01","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8227"},"modified":"2023-06-19T13:30:24","modified_gmt":"2023-06-19T11:30:24","slug":"26-jun-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/26-jun-23\/","title":{"rendered":"Algoritmo divide y vencer\u00e1s"},"content":{"rendered":"<p>La t\u00e9cnica <a href=\"https:\/\/bit.ly\/46afaca\">divide y vencer\u00e1s<\/a> consta de los siguientes pasos:<\/p>\n<ul>\n<li>Dividir el problema en subproblemas menores.<\/li>\n<li>Resolver por separado cada uno de los subproblemas:\n<ul>\n<li>si los subproblemas son complejos, usar la misma t\u00e9cnica recursivamente;<\/li>\n<li>si son simples, resolverlos directamente.<\/li>\n<\/ul>\n<\/li>\n<li>Combinar todas las soluciones de los subproblemas en una soluci\u00f3n simple.<\/li>\n<\/ul>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   divideVenceras :: (p -> Bool)\n                  -> (p -> s)\n                  -> (p -> [p])\n                  -> (p -> [s] -> s)\n                  -> p\n                  -> s\n<\/pre>\n<p>tal que <code>divideVenceras ind resuelve divide combina pbInicial<\/code> resuelve el problema <code>pbInicial<\/code> mediante la t\u00e9cnica de divide y vencer\u00e1s, donde<\/p>\n<ul>\n<li><code>ind pb<\/code> se verifica si el problema <code>pb<\/code> es indivisible<\/li>\n<li><code>resuelve pb<\/code> es la soluci\u00f3n del problema indivisible <code>pb<\/code><\/li>\n<li><code>divide pb<\/code> es la lista de subproblemas de <code>pb<\/code><\/li>\n<li><code>combina pb ss<\/code> es la combinaci\u00f3n de las soluciones <code>ss<\/code> de los subproblemas del problema <code>pb<\/code>.<\/li>\n<li><code>pbInicial<\/code> es el problema inicial<\/li>\n<\/ul>\n<p>Usando la funci\u00f3n DivideVenceras, definir las funciones<\/p>\n<pre lang=\"text\">\n   ordenaPorMezcla :: Ord a => [a] -> [a]\n   ordenaRapida    :: Ord a => [a] -> [a]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li><code>ordenaPorMezcla xs<\/code> es la lista obtenida ordenando <code>xs<\/code> por el procedimiento de ordenaci\u00f3n por mezcla. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> ordenaPorMezcla [3,1,4,1,5,9,2,8]\n     [1,1,2,3,4,5,8,9]\n<\/pre>\n<ul>\n<li><code>ordenaRapida xs<\/code> es la lista obtenida ordenando <code>xs<\/code> por el procedimiento de ordenaci\u00f3n r\u00e1pida. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> ordenaRapida [3,1,4,1,5,9,2,8]\n     [1,1,2,3,4,5,8,9]\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule DivideVenceras (divideVenceras) where\n\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\ndivideVenceras :: (p -> Bool)\n               -> (p -> s)\n               -> (p -> [p])\n               -> (p -> [s] -> s)\n               -> p\n               -> s\ndivideVenceras ind resuelve divide combina = dv'\n  where\n    dv' pb\n      | ind pb    = resuelve pb\n      | otherwise = combina pb [dv' sp | sp <- divide pb]\n\nordenaPorMezcla :: Ord a => [a] -> [a]\nordenaPorMezcla =\n    divideVenceras ind id divide combina\n    where\n      ind xs            = length xs <= 1\n      divide xs         = [take n xs, drop n xs]\n                          where n = length xs `div` 2\n      combina _ [l1,l2] = mezcla l1 l2\n\n-- (mezcla xs ys) es la lista obtenida mezclando xs e ys. Por ejemplo,\n--    mezcla [1,3] [2,4,6]  ==  [1,2,3,4,6]\nmezcla :: Ord a => [a] -> [a] -> [a]\nmezcla [] b = b\nmezcla a [] = a\nmezcla a@(x:xs) b@(y:ys) | x <= y    = x : mezcla xs b\n                         | otherwise = y : mezcla a ys\n\nordenaRapida :: Ord a => [a] -> [a]\nordenaRapida =\n    divideVenceras ind id divide combina\n    where\n      ind xs                = length xs <= 1\n      divide (x:xs)         = [[ y | y <- xs, y <= x],\n                               [ y | y <- xs, y > x]]\n      combina (x:_) [l1,l2] = l1 ++ [x] ++ l2\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    ordenaPorMezcla [3,1,4,1,5,9,2,8] `shouldBe` [1,1,2,3,4,5,8,9]\n  it \"e2\" $\n    ordenaRapida [3,1,4,1,5,9,2,8] `shouldBe` [1,1,2,3,4,5,8,9]\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--\n--    Finished in 0.0004 seconds\n--    2 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom typing import Callable, TypeVar\n\nP = TypeVar('P')\nS = TypeVar('S')\n\ndef divideVenceras(ind: Callable[[P], bool],\n                   resuelve: Callable[[P], S],\n                   divide: Callable[[P], list[P]],\n                   combina: Callable[[P, list[S]], S],\n                   p: P) -> S:\n    def dv(pb: P) -> S:\n        if ind(pb):\n            return resuelve(pb)\n        return combina(pb, [dv(sp) for sp in divide(pb)])\n    return dv(p)\n\ndef ordenaPorMezcla(xs: list[int]) -> list[int]:\n    def ind(xs: list[int]) -> bool:\n        return len(xs) <= 1\n\n    def divide(xs: list[int]) -> list[list[int]]:\n        n = len(xs) \/\/ 2\n        return [xs[:n], xs[n:]]\n\n    def combina(_: list[int], xs: list[list[int]]) -> list[int]:\n        return mezcla(xs[0], xs[1])\n\n    return divideVenceras(ind, lambda x: x, divide, combina, xs)\n\n# (mezcla xs ys) es la lista obtenida mezclando xs e ys. Por ejemplo,\n#    mezcla([1,3], [2,4,6]) == [1,2,3,4,6]\ndef mezcla(a: list[int], b: list[int]) -> list[int]:\n    if not a:\n        return b\n    if not b:\n        return a\n    if a[0] <= b[0]:\n        return [a[0]] + mezcla(a[1:], b)\n    return [b[0]] + mezcla(a, b[1:])\n\ndef ordenaRapida(xs: list[int]) -> list[int]:\n    def ind(xs: list[int]) -> bool:\n        return len(xs) <= 1\n\n    def divide(xs: list[int]) -> list[list[int]]:\n        x, *xs = xs\n        return [[y for y in xs if y <= x],\n                [y for y in xs if y > x]]\n\n    def combina(xs: list[int], ys: list[list[int]]) -> list[int]:\n        x = xs[0]\n        return ys[0] + [x] + ys[1]\n\n    return divideVenceras(ind, lambda x: x, divide, combina, xs)\n\n# Verificaci\u00f3n\n# ============\n\ndef test_divideVenceras() -> None:\n    assert ordenaPorMezcla([3,1,4,1,5,9,2,8]) == [1,1,2,3,4,5,8,9]\n    assert ordenaRapida([3,1,4,1,5,9,2,8]) == [1,1,2,3,4,5,8,9]\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_divideVenceras()\n#    Verificado\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>La t\u00e9cnica divide y vencer\u00e1s consta de los siguientes pasos: Dividir el problema en subproblemas menores. Resolver por separado cada uno de los subproblemas: si los subproblemas son complejos, usar la misma t\u00e9cnica recursivamente; si son simples, resolverlos directamente. Combinar todas las soluciones de los subproblemas en una soluci\u00f3n simple. Definir la funci\u00f3n divideVenceras ::&#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":[581],"tags":[589],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8227"}],"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=8227"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8227\/revisions"}],"predecessor-version":[{"id":8229,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8227\/revisions\/8229"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8227"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8227"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8227"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}