Menu Close

Sumas con sumandos distintos o con sumandos impares

José A. Alonso,

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. Responder
    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. Responder
    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. Responder
    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. Responder
    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. Responder
    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.