Ceros con los n primeros números
Los números del 1 al 3 se pueden escribir de dos formas, con el signo más o menos entre ellos, tales que su suma sea 0:
1 2 |
1+2-3 = 0 -1-2+3 = 0 |
Definir la función
1 |
ceros :: Int -> [[Int]] |
tal que (ceros n) son las posibles formas de obtener cero sumando los números del 1 al n, con el signo más o menos entre ellos. Por ejemplo,
1 2 3 4 5 |
ceros 3 == [[1,2,-3],[-1,-2,3]] ceros 4 == [[1,-2,-3,4],[-1,2,3,-4]] ceros 5 == [] length (ceros 7) == 8 take 3 (ceros 7) == [[1,2,-3,4,-5,-6,7],[1,2,-3,-4,5,6,-7],[1,-2,3,4,-5,6,-7]] |
Soluciones
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 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
-- 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) |
Una pequeña optimización:
En el primer ejemplo da [[2,-3],[-2,3]] en lugar de [[1,2,-3],[-1,-2,3]].
Ya he puesto una corrección en otro comentario.
Lo que sí que no dará será los resultados en el mismo orden que aparecen en los ejemplos. Si se quiere tener el mismo orden se podría hacer así:
Es incorrecto. Falta incorporar la suma al resultado: