Menu Close

Sumas de subconjuntos

Definir la función

   sumasSubconjuntos :: Set Int -> Set Int

tal que (sumasSubconjuntos xs) es el conjunto de las sumas de cada uno de los subconjuntos de xs. Por ejemplo,

   λ> sumasSubconjuntos (fromList [3,2,5])
   fromList [0,2,3,5,7,8,10]
   λ> length (sumasSubconjuntos (fromList [-40,-39..40]))
   1641

Soluciones

import Data.List
import Data.Set ( Set
                , deleteFindMin
                , fromList
                , singleton
                , toList
                )
import qualified Data.Set as S
 
-- 1ª definición
-- =============
 
sumasSubconjuntos :: Set Int -> Set Int
sumasSubconjuntos xs =
  fromList (map sum (subsequences (toList xs))) 
 
-- 2ª definición
-- =============
 
sumasSubconjuntos2 :: Set Int -> Set Int
sumasSubconjuntos2 =
  fromList . sumasSubconjuntosL . toList  
 
sumasSubconjuntosL :: [Int] -> [Int]
sumasSubconjuntosL []     = [0]
sumasSubconjuntosL (x:xs) = ys `union` map (+x) ys
  where ys = sumasSubconjuntosL xs
 
-- 3ª solución
-- ===========
 
sumasSubconjuntos3 :: Set Int -> Set Int
sumasSubconjuntos3 xs
  | S.null xs = singleton 0
  | otherwise = zs `S.union` (S.map (+y) zs)
  where (y,ys) = deleteFindMin xs
        zs     = sumasSubconjuntos2 ys
 
-- Comparación de eficiencia
-- =========================
 
--    λ> length (sumasSubconjuntos (fromList [1..22]))
--    254
--    (4.17 secs, 4,574,495,128 bytes)
--    λ> length (sumasSubconjuntos2 (fromList [1..22]))
--    254
--    (0.03 secs, 5,583,200 bytes)
--    λ> length (sumasSubconjuntos3 (fromList [1..22]))
--    254
--    (0.03 secs, 5,461,064 bytes)
--
--    λ> length (sumasSubconjuntos2 (fromList [1..60]))
--    1831
--    (2.75 secs, 611,912,128 bytes)
--    λ> length (sumasSubconjuntos3 (fromList [1..60]))
--    1831
--    (2.81 secs, 610,476,992 bytes)

4 soluciones de “Sumas de subconjuntos

  1. alerodrod5

    una definición poco eficiente ya que se basa en el paso a listas

     
    import Data.Set as S
    import Data.List
     
    sumasSubconjuntos :: Set Int -> Set Int
    sumasSubconjuntos s= S.map sum (fromList  (subsequences(toList s)))
  2. angruicam1
    import Prelude hiding (map)
    import Data.Set (Set, powerSet, map, fromList)
     
    sumasSubconjuntos :: Set Int -> Set Int
    sumasSubconjuntos = map sum . powerSet
  3. mirmednav
    import Data.Set as S 
     
    sumasSubconjuntos :: Set Int -> Set Int
    sumasSubconjuntos s = aux n (singleton 0)
               where n = size s - 1
                     aux 0 t = suma 0 t
                     aux i t = aux (i-1) (suma i t)
                     suma i t = t `union` S.map (+ elemAt i s) t
  4. Chema Cortés
    import Data.Set as S
     
    sumasSubconjuntos :: Set Int -> Set Int
    sumasSubconjuntos xs | S.null xs = singleton 0
                         | otherwise = zs `union` S.map (y+) zs
      where
        (y,ys) = S.deleteFindMin xs
        zs = sumasSubconjuntos ys

Escribe tu solución

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