{"id":8274,"date":"2023-09-04T06:00:19","date_gmt":"2023-09-04T04:00:19","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8274"},"modified":"2024-05-17T18:49:22","modified_gmt":"2024-05-17T16:49:22","slug":"04-sep-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/04-sep-23\/","title":{"rendered":"Problema de suma cero (con espacios de estados)"},"content":{"rendered":"

El problema de suma cero consiste en, dado el conjunto de enteros, encontrar sus subconjuntos no vac\u00edo cuyos elementos sumen cero.<\/p>\n

Usando el procedimiento de b\u00fasqueda en profundidad<\/a>, definir la funci\u00f3n<\/p>\n

\n   suma0 :: [Int] -> [[Int]]\n<\/pre>\n
tal que suma0 ns<\/code> es la lista de las soluciones del problema de suma cero para ns<\/code>. Por ejemplo,<\/p>\n
\n   \u03bb> suma0 [-7,-3,-2,5,8]\n   [[-3,-2,5]]\n   \u03bb> suma0 [-7,-3,-2,5,8,-1]\n   [[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]]\n   \u03bb> suma0 [-7,-3,1,5,8]\n   []\n<\/pre>\n
<\/p>\n
Soluciones<\/b><\/p>\n
A continuaci\u00f3n se muestran las soluciones en Haskell<\/a> y las soluciones en Python<\/a>.<\/p>\n
<\/a>
\nSoluciones en Haskell<\/b><\/p>\n
\nmodule Problema_de_suma_cero where\n\nimport BusquedaEnProfundidad (buscaProfundidad)\nimport Data.List (delete, nub, sort)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\n-- Los estados son ternas formadas por los n\u00fameros seleccionados, su\n-- suma y los restantes n\u00fameros.\ntype Estado = ([Int], Int, [Int])\n\ninicial :: [Int] -> Estado\ninicial ns = ([],0,ns)\n\nesFinal :: Estado -> Bool\nesFinal (xs,s,_) =\n  not (null xs) && s == 0\n\nsucesores :: Estado -> [Estado]\nsucesores (xs,s,ns) =\n  [(n:xs, n+s, delete n ns) | n <- ns]\n\nsoluciones :: [Int] -> [Estado]\nsoluciones ns =\n  buscaProfundidad sucesores esFinal (inicial ns)\n\nsuma0 :: [Int] -> [[Int]]\nsuma0 ns =\n  nub [sort xs | (xs,_,_) <- soluciones ns]\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"e1\" $\n    suma0 [-7,-3,-2,5,8] `shouldBe`\n    [[-3,-2,5]]\n  it \"e2\" $\n    suma0 [-7,-3,-2,5,8,-1] `shouldBe`\n    [[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]]\n  it \"e3\" $\n    suma0 [-7,-3,1,5,8] `shouldBe`\n    []\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    e1\n--    e2\n--    e3\n--\n--    Finished in 0.0098 seconds\n--    3 examples, 0 failures\n<\/pre>\n
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\nfrom src.BusquedaEnProfundidad import buscaProfundidad\n\n# Los estados son ternas formadas por los n\u00fameros seleccionados, su\n# suma y los restantes n\u00fameros.\nEstado = tuple[list[int], int, list[int]]\n\ndef inicial(ns: list[int]) -> Estado:\n    return ([], 0, ns)\n\ndef esFinal(e: Estado) -> bool:\n    (xs,s,_) = e\n    return xs != [] and s == 0\n\ndef sucesores(e: Estado) -> list[Estado]:\n    (xs, s, ns) = e\n    return [([n] + xs, n + s, [m for m in ns if m !=n])\n            for n in ns]\n\ndef soluciones(ns: list[int]) -> list[Estado]:\n    return buscaProfundidad(sucesores, esFinal, inicial(ns))\n\ndef suma0(ns: list[int]) -> list[list[int]]:\n    xss = [list(sorted(s[0])) for s in soluciones(ns)]\n    r = []\n    for xs in xss:\n        if xs not in r:\n            r.append(xs)\n    return r\n\n# Verificaci\u00f3n\n# ============\n\ndef test_suma0() -> None:\n    assert suma0([-7,-3,-2,5,8]) == \\\n        [[-3,-2,5]]\n    assert suma0([-7,-3,-2,5,8,-1]) == \\\n        [[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]]\n    assert not suma0([-7,-3,1,5,8])\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_suma0()\n#    Verificado\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
El problema de suma cero consiste en, dado el conjunto de enteros, encontrar sus subconjuntos no vac\u00edo cuyos elementos sumen cero. Usando el procedimiento de b\u00fasqueda en profundidad, definir la funci\u00f3n suma0 :: [Int] -> [[Int]] tal que suma0 ns es la lista de las soluciones del problema de suma cero para ns. Por ejemplo,…<\/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":"default","_kad_post_title":"default","_kad_post_layout":"default","_kad_post_sidebar_id":"","_kad_post_content_style":"default","_kad_post_vertical_padding":"default","_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":[456],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8274"}],"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=8274"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8274\/revisions"}],"predecessor-version":[{"id":8581,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8274\/revisions\/8581"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8274"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8274"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8274"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}