Menu Close

Ceros con los n primeros números

José A. Alonso,

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-3 = 0
   -1-2+3 = 0

Definir la función

   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,

   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ª 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)
Medio
, , , , , , , , , ,

7 soluciones de “Ceros con los n primeros números”

  1. Responder
    alerodrod5 
    import Data.List
 
ceros :: Int -> [[Int]]
ceros n =
  (reverse . sort) [xs | xs <- subsequences (take (n*2) enteros)
                       , sum xs == 0
                       , length xs == n
                       , nub (map abs xs) == map abs xs]         
 
enteros :: [Int]
enteros =  concat [separa (x,-x) | x <-[1..]]
  where separa (x,y) = [x,y]
  2. Responder
    carbremor 
    import Data.List
 
ceros :: Int -> [[Int]]
ceros = filter ((== 0) . sum) . mapM (x -> [x, -x]) . enumFromTo 1
 
-- λ> ceros 7
-- [[1,2,-3,4,-5,-6,7],[1,2,-3,-4,5,6,-7],[1,-2,3,4,-5,6,-7],[1,-2,-3,-4,-5,6,7],[-1,2,3,4,5,-6,-7],[-1,2,-3,-4,5,-6,7],[-1,-2,3,4,-5,-6,7],[-1,-2,3,-4,5,6,-7]]
-- (0.01 secs, 296,984 bytes)
    • Responder
      Chema Cortés

      Una pequeña optimización:

      ceros :: Int -> [[Int]]
ceros = filter ((==1).abs.sum) . mapM (x -> [x, -x]) . enumFromTo 2
        • Responder
          Chema Cortés

          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í:

          ceros :: Int -> [[Int]]
ceros n = filter ((==n).abs.last)
        . map (xs -> xs ++ [-sum xs])
        $ mapM (x -> [x, -x]) [1..n-1]
      • Responder
        Chema Cortés

        Es incorrecto. Falta incorporar la suma al resultado:

        ceros :: Int -> [[Int]]
ceros = filter ((==1).abs.head)
      . map (xs -> -sum xs:xs)
      . mapM (x -> [x, -x])
      . enumFromTo 2
  3. Responder
    jaibengue 
     
ceros1 :: Int -> [[Int]]
ceros1 n | n `mod` 4 == 1 = []
         | n `mod` 4 == 2 = []
         | otherwise = sol ++ map (map (*(-1))) sol
  where aux (x:xs) ys r s | s > t     = []
                          | r > t     = []
                          | s == t    = [ys]
                          | otherwise = aux xs (x:ys) r (x+s) ++ aux xs ys (r+x) s
        aux _ ys _ s | s == t    = [ys]
                     | otherwise = []
 
        aLista (x:xs) q@(y:ys) | y == x    = y : aLista xs ys
                               | otherwise = (-x) : aLista xs q
        aLista _ [] = []
 
        sol = map (aLista [1..n]) (aux [n-1,n-2..1] [n] 0 n)
 
        t = n*(n+1) `div` 4

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.