Menu Close

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-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)

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

  1. 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. 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)
    • Chema Cortés

      Una pequeña optimización:

      ceros :: Int -> [[Int]]
      ceros = filter ((==1).abs.sum) . mapM (x -> [x, -x]) . enumFromTo 2
        • 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]
      • 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. 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.