Subconjuntos con suma dada
Sea S un conjunto finito de números enteros positivos y n un número natural. El problema consiste en calcular los subconjuntos de S cuya suma es n.
Definir la función
|
1 |
subconjuntosSuma:: [Int] -> Int -> [[Int]] tal que |
tal que (subconjuntosSuma xs n) es la lista de los subconjuntos de xs cuya suma es n. Por ejemplo,
|
1 2 3 4 5 6 |
λ> subconjuntosSuma [3,34,4,12,5,2] 9 [[4,5],[3,4,2]] λ> subconjuntosSuma [3,34,4,12,5,2] 13 [] λ> length (subconjuntosSuma [1..100] (sum [1..100])) 1 |
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
import Data.Array import qualified Data.Matrix as M import Data.Maybe import Data.List import Test.QuickCheck -- 1ª definición (Calculando todos los subconjuntos) -- ================================================= subconjuntosSuma1 :: [Int] -> Int -> [[Int]] subconjuntosSuma1 xs n = [ys | ys <- subsequences xs, sum ys == n] -- 2ª definición (por recursión) -- ============================= subconjuntosSuma2 :: [Int] -> Int -> [[Int]] subconjuntosSuma2 _ 0 = [[]] subconjuntosSuma2 [] _ = [] subconjuntosSuma2 (x:xs) n | n < x = subconjuntosSuma2 xs n | otherwise = subconjuntosSuma2 xs n ++ [x:ys | ys <- subconjuntosSuma2 xs (n-x)] -- 3ª definición (por programación dinámica) -- ========================================= subconjuntosSuma3 :: [Int] -> Int -> [[Int]] subconjuntosSuma3 xs n = map reverse (matrizSubconjuntosSuma3 xs n ! (length xs,n)) -- (matrizSubconjuntosSuma3 xs m) es la matriz q tal que q(i,j) es la -- lista de los subconjuntos de (take i xs) que suman j. Por ejemplo, -- λ> elems (matrizSubconjuntosSuma3 [1,3,5] 9) -- [[[]],[], [],[], [], [], [], [],[], [], -- [[]],[[1]],[],[], [], [], [], [],[], [], -- [[]],[[1]],[],[[3]],[[3,1]],[], [], [],[], [], -- [[]],[[1]],[],[[3]],[[3,1]],[[5]],[[5,1]],[],[[5,3]],[[5,3,1]]] -- Con las cabeceras, -- 0 1 2 3 4 5 6 7 8 9 -- [] [[[]],[], [],[], [], [], [], [],[], [], -- [1] [[]],[[1]],[],[], [], [], [], [],[], [], -- [1,3] [[]],[[1]],[],[[3]],[[3,1]],[], [], [],[], [], -- [1,3,5] [[]],[[1]],[],[[3]],[[3,1]],[[5]],[[5,1]],[],[[5,3]],[[5,3,1]]] matrizSubconjuntosSuma3 :: [Int] -> Int -> Array (Int,Int) [[Int]] matrizSubconjuntosSuma3 xs n = q where m = length xs v = listArray (1,m) xs q = array ((0,0),(m,n)) [((i,j), f i j) | i <- [0..m], j <- [0..n]] f _ 0 = [[]] f 0 _ = [] f i j | j < v ! i = q ! (i-1,j) | otherwise = q ! (i-1,j) ++ [v!i:ys | ys <- q ! (i-1,j-v!i)] -- 4ª definición (ordenando y por recursión) -- ========================================= subconjuntosSuma4 :: [Int] -> Int -> [[Int]] subconjuntosSuma4 xs = aux (sort xs) where aux _ 0 = [[]] aux [] _ = [] aux (y:ys) n | y > n = [] | otherwise = aux ys n ++ [y:zs | zs <- aux ys (n-y)] -- 5ª definición (ordenando y dinámica) -- ==================================== subconjuntosSuma5 :: [Int] -> Int -> [[Int]] subconjuntosSuma5 xs n = matrizSubconjuntosSuma5 (reverse (sort xs)) n ! (length xs,n) matrizSubconjuntosSuma5 :: [Int] -> Int -> Array (Int,Int) [[Int]] matrizSubconjuntosSuma5 xs n = q where m = length xs v = listArray (1,m) xs q = array ((0,0),(m,n)) [((i,j), f i j) | i <- [0..m], j <- [0..n]] f _ 0 = [[]] f 0 _ = [] f i j | v ! i > j = [] | otherwise = q ! (i-1,j) ++ [v!i:ys | ys <- q ! (i-1,j-v!i)] -- Equivalencia -- ============ prop_subconjuntosSuma :: [Int] -> Int -> Bool prop_subconjuntosSuma xs n = all (`igual` subconjuntosSuma2 ys m) [ subconjuntosSuma3 ys m , subconjuntosSuma4 ys m , subconjuntosSuma5 ys m ] where ys = map (\y -> 1 + abs y) xs m = abs n ordenado = sort . map sort igual xss yss = ordenado xss == ordenado yss -- La comprobación es -- λ> quickCheck prop_subconjuntosSuma -- +++ OK, passed 100 tests. |