Menu Close

Sumas con sumandos distintos o con sumandos impares

El número 6 se puede descomponer de 4 formas distintas como suma con sumandos distintos:

   6 = 1 + 2 + 3
   6 = 1 + 5
   6 = 2 + 4
   6 = 6

y también se puede descomponer de 4 formas distintas como suma con sumandos impares:

   6 = 1 + 1 + 1 + 1 + 1 + 1
   6 = 1 + 1 + 1 + 3
   6 = 1 + 5
   6 = 3 + 3

Definir las siguientes funciones

   sumasSumandosDistintos  :: Integer -> [[Integer]]
   nSumasSumandosDistintos :: Integer -> Int
   sumasSumandosImpares    :: Integer -> [[Integer]]
   nSumasSumandosImpares   :: Integer -> Int
   igualdadDeSumas         :: Integer -> Bool

tales que

  • (sumasSumandosDistintos n) es la lista de las descomposiciones de n como sumas con sumandos distintos. Por ejemplo,
     sumasSumandosDistintos 5  ==  [[1,4],[2,3],[5]]
     sumasSumandosDistintos 6  ==  [[1,2,3],[1,5],[2,4],[6]]
  • (nSumasSumandosDistintos n) es el número de descomposiciones de n como sumas con sumandos distintos. Por ejemplo,
     nSumasSumandosDistintos 6  ==  4
     nSumasSumandosDistintos 7  ==  5
  • (sumasSumandosImpares n) es la lista de las descomposiones de n como sumas con sumandos impares. Por ejemplo,
     sumasSumandosImpares 5  ==  [[1,1,1,1,1],[1,1,3],[5]]
     sumasSumandosImpares 6  ==  [[1,1,1,1,1,1],[1,1,1,3],[1,5],[3,3]]
  • (nSumasSumandosImpares n) es el número de descomposiciones de n como sumas con sumandos impares. Por ejemplo,
     nSumasSumandosImpares 6  ==  4
     nSumasSumandosImpares 7  ==  5
  • (igualdadDeSumas n) se verifica si, para todo k entre 1 y n, las funciones nSumasSumandosDistintos y nSumasSumandosImpares son iguales. Por ejemplo,
     igualdadDeSumas 40  ==  True

Soluciones

import Data.List (delete, nub)
 
-- Definiciones de sumasSumandosDistintos
-- ======================================
 
-- 1ª definición sumasSumandosDistintos
sumasSumandosDistintos :: Integer -> [[Integer]]
sumasSumandosDistintos n = aux n [1..n]
  where aux 0 _ = [[]]
        aux _ [] = []
        aux x ys@(y:_)
          | x < y     = []
          | x == y    = [[x]]
          | otherwise = [z : zs | z <- ys
                                , zs <- aux (x - z) (dropWhile (<=z) ys)]
 
-- 2ª definición de sumasSumandosDistintos
sumasSumandosDistintos2 :: Integer ->[[Integer]]
sumasSumandosDistintos2 = aux 0
  where aux i z
          | z < 0  = []
          | z == 0 = [[]]
          | z > 0  = concat [map (j:) (aux j (z-j)) | j <- [i+1..z]]
 
-- Definición de nSumasSumandosDistintos
-- =====================================
 
nSumasSumandosDistintos :: Integer -> Int
nSumasSumandosDistintos =
  length . sumasSumandosDistintos
 
-- Definiciones de sumasSumandosImpares
-- ====================================
 
-- 1ª definición de sumasSumandosImpares
sumasSumandosImpares :: Integer -> [[Integer]]
sumasSumandosImpares n = aux n [1,3..n]
  where aux n _ | n < 0 = []
        aux 0 _  = [[]]
        aux _ [] = []
        aux x zs@(y:ys) = [y:zs | zs <- aux (x-y) zs] ++ aux x ys 
 
-- 2ª definición de sumasSumandosImpares
sumasSumandosImpares2 :: Integer ->[[Integer]]
sumasSumandosImpares2 = aux 1
  where aux i z
          | z < 0  = []
          | z == 0 = [[]]
          | z > 0  = concat [map (j:) (aux j (z-j)) | j <-[i,i+2..z]]
 
-- Definición de nSumasSumandosImpares
-- ===================================
 
nSumasSumandosImpares :: Integer -> Int
nSumasSumandosImpares =
  length . sumasSumandosImpares
 
-- Definición conjunta (de josejuan)
-- =================================
 
-- podemos definir una gran familia de generadores de la siguiente forma
sumas :: Integer ->Integer ->Integer ->Integer ->Integer ->[[Integer]]
sumas u a b k n = s u n where
  s i z | z < 0 = []
        | z == 0 = [[]]
        | z > 0 = concat [map (j:) (s j (z - j)) | j <-[k*i+a,k*i+b..z]]
 
-- así, si queremos los distintos
sumasSumandosDistintos3 :: Integer ->[[Integer]]
sumasSumandosDistintos3 = sumas 0 1 2 1
 
-- o queremos los impares repetidos
sumasSumandosImpares3 :: Integer ->[[Integer]]
sumasSumandosImpares3 = sumas 1 0 2 1
 
-- Igualdad de las sumas
-- =====================
 
igualdadDeSumas :: Integer -> Bool
igualdadDeSumas n =
  and [nSumasSumandosDistintos k == nSumasSumandosImpares k | k <- [1..n]]
 
-- Comparación de eficiencia
-- =========================
 
--    λ> length (sumasSumandosDistintos2 70)
--    29927
--    (0.57 secs, 374,604,848 bytes)
--    λ> length (sumasSumandosDistintos3 70)
--    29927
--    (0.57 secs, 352,658,200 bytes)
--    λ> length (sumasSumandosImpares 70)
--    29927
--    (8.87 secs, 5,221,638,688 bytes)
--    λ> length (sumasSumandosImpares2 70)
--    29927
--    (0.61 secs, 422,132,696 bytes)
--    λ> length (sumasSumandosImpares3 70)
--    29927
--    (0.56 secs, 412,289,336 bytes)
Avanzado

5 soluciones de “Sumas con sumandos distintos o con sumandos impares

  1. albcercid
    sumasSumandosDistintos  :: Integer -> [[Integer]]
    sumasSumandosDistintos n = linkInPark n n
    linkInPark 0 _ = [[]]
    linkInPark a b =
        concat [map (x:) (linkInPark (a-x) (min (x-1) (a-x))) | x <- [t 1..b]]
         where t x | sum [1..x] < a = t (x+1)
                   | otherwise = x
     
    nSumasSumandosDistintos :: Integer -> Int
    nSumasSumandosDistintos = length.sumasSumandosDistintos
     
    sumasSumandosImpares :: Integer -> [[Integer]]
    sumasSumandosImpares n = gNr n n
    gNr 0 _ = [[]]
    gNr a b =
        concat [map (x:) (gNr (a-x) (min (a-x) x)) | x <- reverse [1,3..b]]
     
     
    nSumasSumandosImpares :: Integer -> Int
    nSumasSumandosImpares = length.sumasSumandosImpares
     
    igualdadDeSumas :: Integer -> Bool
    igualdadDesSumas n = nSumasSumandosImpares n == nSumasSumandosDistintos n
  2. josejuan
    -- podemos definir una gran familia de generadores de la siguiente forma
    sumas :: Integer ->Integer ->Integer ->Integer ->Integer ->[[Integer]]
    sumas u a b k n = s u n where
      s i z | z < 0 = []
            | z == 0 = [[]]
            | z > 0 = concat [map (j:) (s j (z - j)) | j <-[k*i+a,k*i+b..z]]
     
    -- así, si queremos los distintos
    sumasSumandosDistintos :: Integer ->[[Integer]]
    sumasSumandosDistintos = sumas 0 1 2 1
     
    -- o queremos los impares repetidos
    sumasSumandosImpares :: Integer ->[[Integer]]
    sumasSumandosImpares = sumas 1 0 2 1
     
    -- o sin repetir
    sumasSumandosImparesDistintos = sumas (-1) 2 4 1
     
    -- o los pares
    sumasSumandosPares          = sumas 2 0 2 1
    sumasSumandosParesDistintos = sumas 0 2 4 1
     
    -- etc...
  3. cescarde
    parts :: (Enum a, Num a, Ord a) => a -> [[a]]
    parts 0 = [[]] 
    parts n = [m:p | m<-[1..n], p<-parts (n-m), null p || m<=head p]
     
    diff :: Eq a => [[a]] -> [[a]]
    diff [] = []
    diff (x:xs) | l x == l (nub x) = x : diff xs
                | otherwise = diff xs
                  where l = length
     
    oddy :: (Integral a, Foldable t) => [t a] -> [t a]
    oddy [] = []
    oddy (x:xs) | all odd x = x : oddy xs
                | otherwise = oddy xs
     
    sumasSumandosDistintos :: Integer -> [[Integer]]
    sumasSumandosDistintos = diff.parts
     
    nSumasSumandosDistintos :: Integer -> Int
    nSumasSumandosDistintos = length.sumasSumandosDistintos
     
    sumasSumandosImpares :: Integer -> [[Integer]]
    sumasSumandosImpares = oddy.parts
     
    nSumasSumandosImpares :: Integer -> Int
    nSumasSumandosImpares = length.sumasSumandosImpares
     
    igualdadDeSumas :: Integer -> Bool
    igualdadDeSumas n = nSumasSumandosDistintos n == nSumasSumandosImpares n
  4. monlagare
     
    sumasSumandosDistintos  :: Integer -> [[Integer]]
    sumasSumandosDistintos n = (filter p xss) ++ [[n]]
          where xss = (subsequences [1..(n-1)])
                p xs = sum xs == n
     
    nSumasSumandosDistintos :: Integer -> Int
    nSumasSumandosDistintos = length.sumasSumandosDistintos
  5. enrnarbej
    -- Se puede obtener la descomposición en sumandos impares a partir de la
    -- descomposición en sumandos distintos 
     
    sumasSumandosImpares :: Integer -> [[Integer]]
    sumasSumandosImpares = map (concatMap aux) . sumasSumandosDistintos
      where
        aux x | odd  x    = [x]
              | otherwise = head [replicate (fromInteger (x `div` n)) n
                                 | n <- [x-1,x-3..1]
                                 , x `mod` n == 0]
     
    -- Lo interesante sería encontrar otra relación pero de sentido
    -- contrario, lo cual nos permitiría probar la propiedad

Escribe tu solución

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