Sumas de subconjuntos

Definir la función

   sumasSubconjuntos :: Set Int -> Set Int

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,

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

λ> 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)

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 Comentarios

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)))

import Data.Set as S

import Data.List

sumasSubconjuntos :: Set Int -> Set Int

sumasSubconjuntos s= S.map sum (fromList (subsequences(toList s)))

Responder

import Prelude hiding (map)
import Data.Set (Set, powerSet, map, fromList)

sumasSubconjuntos :: Set Int -> Set Int
sumasSubconjuntos = map sum . powerSet

import Prelude hiding (map)

import Data.Set (Set, powerSet, map, fromList)

sumasSubconjuntos :: Set Int -> Set Int

sumasSubconjuntos = map sum . powerSet

Responder

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

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

Responder

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

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

Responder

Sumas de subconjuntos

Soluciones

4 Comentarios

Leave a Reply to mirmednavCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

4 Comentarios

Leave a Reply to mirmednavCancel reply

Entradas recientes

Buscar

Correo electrónico