Sumas de subconjuntos
Definir la función
|
1 |
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,
|
1 2 3 4 |
λ> sumasSubconjuntos (fromList [3,2,5]) fromList [0,2,3,5,7,8,10] λ> length (sumasSubconjuntos (fromList [-40,-39..40])) 1641 |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
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) |