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)