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 |