Problema de suma cero (con espacios de estados)
El problema de suma cero consiste en, dado el conjunto de enteros, encontrar sus subconjuntos no vacío cuyos elementos sumen cero.
Usando el procedimiento de búsqueda en profundidad, definir la función
|
1 |
suma0 :: [Int] -> [[Int]] |
tal que suma0 ns es la lista de las soluciones del problema de suma cero para ns. Por ejemplo,
|
1 2 3 4 5 6 |
λ> suma0 [-7,-3,-2,5,8] [[-3,-2,5]] λ> suma0 [-7,-3,-2,5,8,-1] [[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]] λ> suma0 [-7,-3,1,5,8] [] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
module Problema_de_suma_cero where import BusquedaEnProfundidad (buscaProfundidad) import Data.List (delete, nub, sort) import Test.Hspec (Spec, hspec, it, shouldBe) -- Los estados son ternas formadas por los números seleccionados, su -- suma y los restantes números. type Estado = ([Int], Int, [Int]) inicial :: [Int] -> Estado inicial ns = ([],0,ns) esFinal :: Estado -> Bool esFinal (xs,s,_) = not (null xs) && s == 0 sucesores :: Estado -> [Estado] sucesores (xs,s,ns) = [(n:xs, n+s, delete n ns) | n <- ns] soluciones :: [Int] -> [Estado] soluciones ns = buscaProfundidad sucesores esFinal (inicial ns) suma0 :: [Int] -> [[Int]] suma0 ns = nub [sort xs | (xs,_,_) <- soluciones ns] -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ suma0 [-7,-3,-2,5,8] `shouldBe` [[-3,-2,5]] it "e2" $ suma0 [-7,-3,-2,5,8,-1] `shouldBe` [[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]] it "e3" $ suma0 [-7,-3,1,5,8] `shouldBe` [] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- -- Finished in 0.0098 seconds -- 3 examples, 0 failures |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
from src.BusquedaEnProfundidad import buscaProfundidad # Los estados son ternas formadas por los números seleccionados, su # suma y los restantes números. Estado = tuple[list[int], int, list[int]] def inicial(ns: list[int]) -> Estado: return ([], 0, ns) def esFinal(e: Estado) -> bool: (xs,s,_) = e return xs != [] and s == 0 def sucesores(e: Estado) -> list[Estado]: (xs, s, ns) = e return [([n] + xs, n + s, [m for m in ns if m !=n]) for n in ns] def soluciones(ns: list[int]) -> list[Estado]: return buscaProfundidad(sucesores, esFinal, inicial(ns)) def suma0(ns: list[int]) -> list[list[int]]: xss = [list(sorted(s[0])) for s in soluciones(ns)] r = [] for xs in xss: if xs not in r: r.append(xs) return r # Verificación # ============ def test_suma0() -> None: assert suma0([-7,-3,-2,5,8]) == \ [[-3,-2,5]] assert suma0([-7,-3,-2,5,8,-1]) == \ [[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]] assert not suma0([-7,-3,1,5,8]) print("Verificado") # La verificación es # >>> test_suma0() # Verificado |