Decidir si existe un subconjunto con suma dada
Sea S un conjunto finito de números naturales y m un número natural. El problema consiste en determinar si existe un subconjunto de S cuya suma es m. Por ejemplo, si S = [3,34,4,12,5,2] y m = 9, existe un subconjunto de S, [4,5], cuya suma es 9. En cambio, no hay ningún subconjunto de S que sume 13.
Definir la función
|
1 |
existeSubSuma :: [Int] -> Int -> Bool |
tal que (existeSubSuma xs m) se verifica si existe algún subconjunto de xs que sume m. Por ejemplo,
|
1 2 3 4 5 |
existeSubSuma [3,34,4,12,5,2] 9 == True existeSubSuma [3,34,4,12,5,2] 13 == False existeSubSuma ([3,34,4,12,5,2]++[20..400]) 13 == False existeSubSuma ([3,34,4,12,5,2]++[20..400]) 654 == True existeSubSuma [1..200] (sum [1..200]) == True |
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 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 |
import Data.List (subsequences, sort) import Data.Array (Array, array, listArray, (!)) -- 1ª definición (Calculando todos los subconjuntos) -- ================================================= existeSubSuma1 :: [Int] -> Int -> Bool existeSubSuma1 xs n = any (\ys -> sum ys == n) (subsequences xs) -- 2ª definición (por recursión) -- ============================= existeSubSuma2 :: [Int] -> Int -> Bool existeSubSuma2 _ 0 = True existeSubSuma2 [] _ = False existeSubSuma2 (x:xs) n | n < x = existeSubSuma2 xs n | otherwise = existeSubSuma2 xs (n-x) || existeSubSuma2 xs n -- 3ª definición (por programación dinámica) -- ========================================= existeSubSuma3 :: [Int] -> Int -> Bool existeSubSuma3 xs n = matrizExisteSubSuma3 xs n ! (length xs,n) -- (matrizExisteSubSuma3 xs m) es la matriz q tal que q(i,j) se verifica -- si existe algún subconjunto de (take i xs) que sume j. Por ejemplo, -- λ> elems (matrizExisteSubSuma3 [1,3,5] 9) -- [True,False,False,False,False,False,False,False,False,False, -- True,True, False,False,False,False,False,False,False,False, -- True,True, False,True, True, False,False,False,False,False, -- True,True, False,True, True, True, True, False,True, True] -- Con las cabeceras, -- 0 1 2 3 4 5 6 7 8 9 -- [] [True,False,False,False,False,False,False,False,False,False, -- [1] True,True, False,False,False,False,False,False,False,False, -- [1,3] True,True, False,True, True, False,False,False,False,False, -- [1,3,5] True,True, False,True, True, True, True, False,True, True] matrizExisteSubSuma3 :: [Int] -> Int -> Array (Int,Int) Bool matrizExisteSubSuma3 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 = True f 0 _ = False f i j | j < v ! i = q ! (i-1,j) | otherwise = q ! (i-1,j-v!i) || q ! (i-1,j) -- 4ª definición (ordenando y por recursión) -- ========================================= existeSubSuma4 :: [Int] -> Int -> Bool existeSubSuma4 xs = aux (sort xs) where aux _ 0 = True aux [] _ = False aux (y:ys) n | y <= n = aux ys (n-y) || aux ys n | otherwise = False -- 5ª definición (ordenando y dinámica) -- ==================================== existeSubSuma5 :: [Int] -> Int -> Bool existeSubSuma5 xs n = matrizExisteSubSuma5 (reverse (sort xs)) n ! (length xs,n) matrizExisteSubSuma5 :: [Int] -> Int -> Array (Int,Int) Bool matrizExisteSubSuma5 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 = True f 0 _ = False f i j | v ! i <= j = q ! (i-1,j-v!i) || q ! (i-1,j) | otherwise = False -- Equivalencia -- ============ prop_existeSubSuma :: [Int] -> Int -> Bool prop_existeSubSuma xs n = all (== existeSubSuma2 ys m) [ existeSubSuma3 ys m , existeSubSuma4 ys m , existeSubSuma5 ys m ] where ys = map abs xs m = abs n -- La comprobación es -- λ> quickCheck prop_existeSubSuma -- +++ OK, passed 100 tests. -- Comparación de eficiencia: -- ========================== -- λ> let xs = [1..22] in existeSubSuma1 xs (sum xs) -- True -- (7.76 secs, 3,892,403,928 bytes) -- λ> let xs = [1..22] in existeSubSuma2 xs (sum xs) -- True -- (0.02 secs, 95,968 bytes) -- λ> let xs = [1..22] in existeSubSuma3 xs (sum xs) -- True -- (0.03 secs, 6,055,200 bytes) -- λ> let xs = [1..22] in existeSubSuma4 xs (sum xs) -- True -- (0.01 secs, 98,880 bytes) -- λ> let xs = [1..22] in existeSubSuma5 xs (sum xs) -- True -- (0.02 secs, 2,827,560 bytes) -- λ> let xs = [1..200] in existeSubSuma2 xs (sum xs) -- True -- (0.01 secs, 182,280 bytes) -- λ> let xs = [1..200] in existeSubSuma3 xs (sum xs) -- True -- (8.89 secs, 1,875,071,968 bytes) -- λ> let xs = [1..200] in existeSubSuma4 xs (sum xs) -- True -- (0.02 secs, 217,128 bytes) -- λ> let xs = [1..200] in existeSubSuma5 xs (sum xs) -- True -- (8.66 secs, 1,875,087,976 bytes) -- -- λ> and [existeSubSuma2 [1..20] n | n <- [1..sum [1..20]]] -- True -- (2.82 secs, 323,372,512 bytes) -- λ> and [existeSubSuma3 [1..20] n | n <- [1..sum [1..20]]] -- True -- (0.65 secs, 221,806,376 bytes) -- λ> and [existeSubSuma4 [1..20] n | n <- [1..sum [1..20]]] -- True -- (4.12 secs, 535,153,152 bytes) -- λ> and [existeSubSuma5 [1..20] n | n <- [1..sum [1..20]]] -- True -- (0.73 secs, 238,579,696 bytes) |
Una definición no muy eficiente pero funciona