-- 1ª solución
-- ===========
ceros :: Int -> [[Int]]
ceros n = [xs | xs <- candidatos n, sum xs == 0]
-- (candidatos n) es la lista de los números del 1 al n con los signos
-- más o menos. Por ejemplo,
-- λ> candidatos 1
-- [[1],[-1]]
-- λ> candidatos 2
-- [[1,2],[1,-2],[-1,2],[-1,-2]]
-- λ> candidatos 3
-- [[1,2,3],[1,2,-3],[1,-2,3],[1,-2,-3],[-1,2,3],[-1,2,-3],[-1,-2,3],[-1,-2,-3]]
candidatos :: Int -> [[Int]]
candidatos n = productoCartesiano [[i,-i] | i <- [1..n]]
-- (productoCartesiano xss) es el producto cartesiano de los conjuntos
-- xss. Por ejemplo,
-- λ> productoCartesiano [[1,3],[2,5],[6,4]]
-- [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]]
productoCartesiano :: [[a]] -> [[a]]
productoCartesiano [] = [[]]
productoCartesiano (xs:xss) =
[x:ys | x <- xs, ys <- productoCartesiano xss]
-- 2ª solución
-- ===========
ceros2 :: Int -> [[Int]]
ceros2 n = [xs | xs <- candidatos2 n, sum xs == 0]
candidatos2 :: Int -> [[Int]]
candidatos2 n = mapM (\i -> [i,-i]) [1..n]
-- 3ª solución
-- ===========
ceros3 :: Int -> [[Int]]
ceros3 n = [xs | xs <- mapM (\i -> [i,-i]) [1..n], sum xs == 0]
-- 4ª solución
-- ===========
ceros4 :: Integer -> [[Integer]]
ceros4 = map fst
. filter ((==0) . snd)
. sumas
-- (sumas n) es la lista de las candidatos con los n primeros números y
-- sus sumas. Por ejemplo,
-- λ> sumas 2
-- [([1,2],3),([-1,2],1),([1,-2],-1),([-1,-2],-3)]
-- λ> sumas 3
-- [([1,2,3],6),([-1,2,3],4),([1,-2,3],2),([-1,-2,3],0),([1,2,-3],0),
-- ([-1,2,-3],-2),([1,-2,-3],-4),([-1,-2,-3],-6)]
sumas :: Integer -> [([Integer],Integer)]
sumas = foldr aux [([], 0)]
. enumFromTo 1
where
aux n = concatMap (\(ns', s') -> [(n : ns', s' + n), (-n : ns', s' - n)])
-- Comparación de eficiencia
-- =========================
-- λ> length (ceros 18)
-- 0
-- (4.14 secs, 1,094,854,776 bytes)
-- λ> length (ceros2 18)
-- 0
-- (1.16 secs, 375,541,680 bytes)
-- λ> length (ceros3 18)
-- 0
-- (1.13 secs, 375,540,192 bytes)
-- λ> length (ceros4 18)
-- 0
-- (0.69 secs, 157,316,688 bytes) |