Menu Close

Suma de subconjuntos

José A. Alonso,

Los subconjuntos de [1, 4, 2] son

   [], [1], [4], [1, 4], [2], [1, 2], [4, 2], [1, 4, 2]

Las sumas de sus elementos son

   0, 1, 4, 5, 2, 3, 6, 7

Y la suma de las sumas es 28.

Definir la función

   sumaSubconjuntos :: [Integer] -> Integer

tal que (sumaSubconjuntos xs) es la suma de las sumas de los
subconjuntos de xs. Por ejemplo,

   sumaSubconjuntos [1,2]                     == 6
   sumaSubconjuntos [1,4,2]                   == 28
   length (show (sumaSubconjuntos [1..10^6])) == 301042

Soluciones

import Data.List (subsequences)
 
-- 1ª definición
sumaSubconjuntos :: [Integer] -> Integer
sumaSubconjuntos xs =
  sum [sum ys | ys <- subsequences xs]
 
-- 2ª definición
sumaSubconjuntos2 :: [Integer] -> Integer
sumaSubconjuntos2 =
  sum . map sum . subsequences
 
-- 3ª definición
sumaSubconjuntos3 :: [Integer] -> Integer
sumaSubconjuntos3 xs =
  2^(n-1) * sum xs
  where n = length xs
Inicial
, , , ,

7 soluciones de “Suma de subconjuntos”

  1. Responder
    albcercid 
    sumaSubconjuntos :: [Integer] -> Integer
sumaSubconjuntos xs = 2^t*sum xs
     where t = length xs - 1
  2. Responder
    ignareeva 
    sumaSubconjuntos :: [Integer] -> Integer
sumaSubconjuntos xs = sum (map (sum) (subsequences xs))
  3. Responder
    javcancif

    sumaSubconjuntos :: [Integer] -> Integer
    sumaSubconjuntos xs = sum . map (sum) (subquences xs)

    • Responder
      ignareeva

      La función subquences no existe. A lo mejor has querido decir subsequences.

  4. Responder
    alvfercen 
    sumaSubconjuntos :: [Integer] -> Integer
sumaSubconjuntos xs = sum $ map (sum) (subsequences xs)
  5. Responder
    Miguel Ibáñez (migibagar) 
     
sumaSubconjuntos :: [Integer] -> Integer
sumaSubconjuntos xs = n * (foldr (+) 0 xs)
  where n = 2^(length xs - 1)
  6. Responder
    Juanjo Ortega (juaorture) 
     
-- Suma de subconjuntos utilizando el triángulo de Pascal
pascal :: [[Integer]]
pascal = [1] : map (1:) [ ys ++ [1] | ys <- map aux pascal ]
       where aux (x:y:xs) = x+y : aux (y:xs)
             aux _        = []
 
sumaSubconjuntos :: [Integer] -> Integer
sumaSubconjuntos xs = sum (pascal!!(length xs - 1)) * sum xs

Escribe tu solución

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