Problema de suma cero

José A. Alonso

04-09-2023

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

   suma0 :: [Int] -> [[Int]]

tal que suma0 ns es la lista de las soluciones del problema de suma cero para ns. Por ejemplo,

   λ> 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.

Soluciones en Haskell

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

Soluciones en Python

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