{"id":4005,"date":"2018-04-25T06:06:50","date_gmt":"2018-04-25T04:06:50","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=4005"},"modified":"2018-05-02T19:05:34","modified_gmt":"2018-05-02T17:05:34","slug":"subconjuntos-con-suma-dada","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/subconjuntos-con-suma-dada\/","title":{"rendered":"Subconjuntos con suma dada"},"content":{"rendered":"<p>Sea S un conjunto finito de n\u00fameros enteros positivos y n un n\u00famero natural. El problema consiste en calcular los subconjuntos  de S cuya suma es n.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   subconjuntosSuma:: [Int] -> Int -> [[Int]] tal que\n<\/pre>\n<p>tal que (subconjuntosSuma xs n) es la lista de los subconjuntos de xs cuya suma es n. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> subconjuntosSuma [3,34,4,12,5,2] 9\n   [[4,5],[3,4,2]]\n   \u03bb> subconjuntosSuma [3,34,4,12,5,2] 13\n   []\n   \u03bb> length (subconjuntosSuma [1..100] (sum [1..100]))\n   1\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Array\nimport qualified Data.Matrix as M\nimport Data.Maybe\nimport Data.List\nimport Test.QuickCheck\n\n-- 1\u00aa definici\u00f3n (Calculando todos los subconjuntos)\n-- =================================================\n\nsubconjuntosSuma1 :: [Int] -> Int -> [[Int]]\nsubconjuntosSuma1 xs n =\n  [ys | ys <- subsequences xs, sum ys == n]\n\n-- 2\u00aa definici\u00f3n (por recursi\u00f3n)\n-- =============================\n\nsubconjuntosSuma2 :: [Int] -> Int -> [[Int]]\nsubconjuntosSuma2 _  0 = [[]]\nsubconjuntosSuma2 [] _ = []\nsubconjuntosSuma2 (x:xs) n\n  | n < x     = subconjuntosSuma2 xs n\n  | otherwise = subconjuntosSuma2 xs n ++\n                [x:ys | ys <- subconjuntosSuma2 xs (n-x)]\n\n-- 3\u00aa definici\u00f3n (por programaci\u00f3n din\u00e1mica)\n-- =========================================\n\nsubconjuntosSuma3 :: [Int] -> Int -> [[Int]]\nsubconjuntosSuma3 xs n =\n  map reverse (matrizSubconjuntosSuma3 xs n ! (length xs,n))\n\n-- (matrizSubconjuntosSuma3 xs m) es la matriz q tal que q(i,j) es la\n-- lista de los subconjuntos de (take i xs) que suman j. Por ejemplo,\n--    \u03bb> elems (matrizSubconjuntosSuma3 [1,3,5] 9)\n--    [[[]],[],   [],[],   [],     [],   [],     [],[],    [],\n--     [[]],[[1]],[],[],   [],     [],   [],     [],[],    [],\n--     [[]],[[1]],[],[[3]],[[3,1]],[],   [],     [],[],    [],\n--     [[]],[[1]],[],[[3]],[[3,1]],[[5]],[[5,1]],[],[[5,3]],[[5,3,1]]]\n-- Con las cabeceras,\n--            0    1     2  3     4       5     6       7  8       9 \n--    []     [[[]],[],   [],[],   [],     [],   [],     [],[],    [],\n--    [1]     [[]],[[1]],[],[],   [],     [],   [],     [],[],    [],\n--    [1,3]   [[]],[[1]],[],[[3]],[[3,1]],[],   [],     [],[],    [],\n--    [1,3,5] [[]],[[1]],[],[[3]],[[3,1]],[[5]],[[5,1]],[],[[5,3]],[[5,3,1]]]\nmatrizSubconjuntosSuma3 :: [Int] -> Int -> Array (Int,Int) [[Int]]\nmatrizSubconjuntosSuma3 xs n = q\n  where m = length xs\n        v = listArray (1,m) xs\n        q = array ((0,0),(m,n)) [((i,j), f i j) | i <- [0..m],\n                                                  j <- [0..n]]\n        f _ 0 = [[]]\n        f 0 _ = []\n        f i j | j < v ! i = q ! (i-1,j)\n              | otherwise = q ! (i-1,j) ++\n                            [v!i:ys | ys <- q ! (i-1,j-v!i)]\n\n-- 4\u00aa definici\u00f3n (ordenando y por recursi\u00f3n)\n-- =========================================\n\nsubconjuntosSuma4 :: [Int] -> Int -> [[Int]]\nsubconjuntosSuma4 xs = aux (sort xs)\n  where aux _  0 = [[]]\n        aux [] _ = []\n        aux (y:ys) n\n          | y > n     = []\n          | otherwise = aux ys n ++ [y:zs | zs <- aux ys (n-y)]\n\n-- 5\u00aa definici\u00f3n (ordenando y din\u00e1mica)\n-- ====================================\n\nsubconjuntosSuma5 :: [Int] -> Int -> [[Int]]\nsubconjuntosSuma5 xs n =\n  matrizSubconjuntosSuma5 (reverse (sort xs)) n ! (length xs,n)\n\nmatrizSubconjuntosSuma5 :: [Int] -> Int -> Array (Int,Int) [[Int]]\nmatrizSubconjuntosSuma5 xs n = q\n  where m = length xs\n        v = listArray (1,m) xs\n        q = array ((0,0),(m,n)) [((i,j), f i j) | i <- [0..m],\n                                                  j <- [0..n]]\n        f _ 0 = [[]]\n        f 0 _ = []\n        f i j | v ! i > j = []\n              | otherwise = q ! (i-1,j) ++\n                            [v!i:ys | ys <- q ! (i-1,j-v!i)]\n\n-- Equivalencia\n-- ============\n\nprop_subconjuntosSuma :: [Int] -> Int -> Bool\nprop_subconjuntosSuma xs n =\n  all (`igual` subconjuntosSuma2 ys m) [ subconjuntosSuma3 ys m\n                                       , subconjuntosSuma4 ys m\n                                       , subconjuntosSuma5 ys m ]\n  where ys = map (\\y -> 1 + abs y) xs \n        m  = abs n\n        ordenado = sort . map sort\n        igual xss yss = ordenado xss == ordenado yss\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_subconjuntosSuma\n--    +++ OK, passed 100 tests.\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Sea S un conjunto finito de n\u00fameros enteros positivos y n un n\u00famero natural. El problema consiste en calcular los subconjuntos de S cuya suma es n. Definir la funci\u00f3n subconjuntosSuma:: [Int] -> Int -> [[Int]] tal que tal que (subconjuntosSuma xs n) es la lista de los subconjuntos de xs cuya suma es n&#8230;.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[4],"tags":[250,8,286,28,72,10,11,6,32,14,88,40],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4005"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=4005"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4005\/revisions"}],"predecessor-version":[{"id":4032,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4005\/revisions\/4032"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4005"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4005"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4005"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}