Mayores sublistas crecientes
Definir las funciones
1 2 |
mayoresCrecientes :: Ord a => [a] -> [[a]] longitudMayorSublistaCreciente :: Ord a => [a] -> Int |
tales que
- (mayoresCrecientes xs) es la lista de las sublistas crecientes de xs de mayor longitud. Por ejemplo,
1 2 3 4 5 6 7 8 |
λ> mayoresCrecientes [3,2,6,4,5,1] [[3,4,5],[2,4,5]] λ> mayoresCrecientes [10,22,9,33,21,50,41,60,80] [[10,22,33,50,60,80],[10,22,33,41,60,80]] λ> mayoresCrecientes [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15] [[0,4,6,9,13,15],[0,2,6,9,13,15],[0,4,6,9,11,15],[0,2,6,9,11,15]] λ> length (head (mayoresCrecientes (show (2^70)))) 5 |
- (longitudMayorSublistaCreciente xs) es el máximo de las longitudes de las sublistas crecientes de xs. Por ejemplo,
1 2 3 4 5 6 7 8 9 10 |
λ> longitudMayorSublistaCreciente [3,2,6,4,5,1] 3 λ> longitudMayorSublistaCreciente [10,22,9,33,21,50,41,60,80] 6 λ> longitudMayorSublistaCreciente [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15] 6 λ> longitudMayorSublistaCreciente [1..2000] 2000 λ> longitudMayorSublistaCreciente [2000,1999..1] 1 |
Soluciones
[schedule expon=’2017-06-08′ expat=»06:00″]
- Las soluciones se pueden escribir en los comentarios hasta el 08 de junio.
- El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>
[/schedule]
[schedule on=’2017-06-08′ at=»06:00″]
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 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 |
import Data.List (nub, sort, subsequences) import Data.Array -- 1ª definición de mayoresCrecientes -- ================================== mayoresCrecientes1 :: Ord a => [a] -> [[a]] mayoresCrecientes1 xs = [ys | ys <- xss , length ys == m] where xss = sublistasCrecientes xs m = maximum (map length xss) -- (sublistasCrecientes1 xs) es la lista de las sublistas crecientes de -- xs. Por ejemplo, -- λ> sublistasCrecientes [3,2,5] -- [[],[3],[2],[5],[3,5],[2,5]] sublistasCrecientes :: Ord a => [a] -> [[a]] sublistasCrecientes xs = [ys | ys <- subsequences xs , esCreciente ys] -- (esCreciente xs) se verifica si la lista xs es creciente. Por -- ejemplo, -- esCreciente [2,3,5] == True -- esCreciente [2,3,1] == False -- esCreciente [2,3,3] == False esCreciente :: Ord a => [a] -> Bool esCreciente (x:y:zs) = x < y && esCreciente (y:zs) esCreciente _ = True -- 2ª definición de mayoresCrecientes -- ================================== mayoresCrecientes2 :: Ord a => [a] -> [[a]] mayoresCrecientes2 xs = [ys | ys <- xss , length ys == m] where xss = sublistasCrecientes2 xs m = maximum (map length xss) -- (sublistasCrecientes2 xs) es la lista de las sublistas crecientes de -- xs. Por ejemplo, -- λ> sublistasCrecientes2 [3,2,5] -- [[3,5],[3],[2,5],[2],[5],[]] sublistasCrecientes2 :: Ord a => [a] -> [[a]] sublistasCrecientes2 [] = [[]] sublistasCrecientes2 (x:xs) = [x:ys | ys <- yss, null ys || x < head ys] ++ yss where yss = sublistasCrecientes2 xs -- Comparación de eficiencia -- ========================= -- λ> length (head (mayoresCrecientes1 (show (2^70)))) -- 5 -- (10.93 secs, 1,958,822,896 bytes) -- λ> length (head (mayoresCrecientes2 (show (2^70)))) -- 5 -- (0.02 secs, 0 bytes) -- 1ª definición de longitudMayorSublistaCreciente -- =============================================== longitudMayorSublistaCreciente1 :: Ord a => [a] -> Int longitudMayorSublistaCreciente1 = length . head . mayoresCrecientes1 -- 2ª definición de longitudMayorSublistaCreciente -- =============================================== longitudMayorSublistaCreciente2 :: Ord a => [a] -> Int longitudMayorSublistaCreciente2 = length . head . mayoresCrecientes2 -- Comparación de eficiencia: -- λ> longitudMayorSublistaCreciente1 (show (2^70)) -- 5 -- (10.78 secs, 1,969,452,328 bytes) -- λ> longitudMayorSublistaCreciente2 (show (2^70)) -- 5 -- (0.02 secs, 0 bytes) -- 3ª definición de longitudMayorSublistaCreciente -- =============================================== longitudMayorSublistaCreciente3 :: Ord a => [a] -> Int longitudMayorSublistaCreciente3 xs = longitudSCM xs (sort (nub xs)) -- (longitudSCM xs ys) es la longitud de la subsecuencia máxima de xs e -- ys. Por ejemplo, -- longitudSCM "amapola" "matamoscas" == 4 -- longitudSCM "atamos" "matamoscas" == 6 -- longitudSCM "aaa" "bbbb" == 0 longitudSCM :: Eq a => [a] -> [a] -> Int longitudSCM xs ys = (matrizLongitudSCM xs ys) ! (n,m) where n = length xs m = length ys -- (matrizLongitudSCM2 xs ys) es la matriz de orden (n+1)x(m+1) (donde n -- y m son los números de elementos de xs e ys, respectivamente) tal que -- el valor en la posición (i,j) es la longitud de la SCM de los i -- primeros elementos de xs y los j primeros elementos de ys. Por ejemplo, -- λ> elems (matrizLongitudSCM "amapola" "matamoscas") -- [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,2,2,2,2,2,2, -- 0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,3,3,3,3,3, -- 0,1,2,2,2,2,3,3,3,3,3,0,1,2,2,3,3,3,3,3,4,4] -- Gráficamente, -- m a t a m o s c a s -- [0,0,0,0,0,0,0,0,0,0,0, -- a 0,0,1,1,1,1,1,1,1,1,1, -- m 0,1,1,1,1,2,2,2,2,2,2, -- a 0,1,2,2,2,2,2,2,2,3,3, -- p 0,1,2,2,2,2,2,2,2,3,3, -- o 0,1,2,2,2,2,3,3,3,3,3, -- l 0,1,2,2,2,2,3,3,3,3,3, -- a 0,1,2,2,3,3,3,3,3,4,4] matrizLongitudSCM :: Eq a => [a] -> [a] -> Array (Int,Int) Int matrizLongitudSCM xs ys = q where n = length xs m = length ys v = listArray (1,n) xs w = listArray (1,m) ys q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]] where f 0 _ = 0 f _ 0 = 0 f i j | v ! i == w ! j = 1 + q ! (i-1,j-1) | otherwise = max (q ! (i-1,j)) (q ! (i,j-1)) -- Comparación de eficiencia -- ------------------------- -- λ> longitudMayorSublistaCreciente2 [1..22] -- 22 -- (19.63 secs, 2,271,936,784 bytes) -- λ> longitudMayorSublistaCreciente3 [1..22] -- 22 -- (0.01 secs, 0 bytes) -- 4ª definición de longitudMayorSublistaCreciente -- =============================================== longitudMayorSublistaCreciente4 :: Ord a => [a] -> Int longitudMayorSublistaCreciente4 xs = maximum (elems (vectorlongitudMayorSublistaCreciente xs)) -- (vectorlongitudMayorSublistaCreciente xs) es el vector de longitud n -- tal que el valor i-ésimo es la longitud de la sucesión más largar que -- termina en el elemento i-ésimo de xs. Por ejemplo, -- λ> vectorlongitudMayorSublistaCreciente [3,2,6,4,5,1] -- array (1,6) [(1,1),(2,1),(3,2),(4,2),(5,3),(6,1)] vectorlongitudMayorSublistaCreciente :: Ord a => [a] -> Array Int Int vectorlongitudMayorSublistaCreciente xs = v where v = array (1,n) [(i,f i) | i <- [1..n]] n = length xs w = listArray (1,n) xs f 1 = 1 f i | null ls = 1 | otherwise = 1 + maximum ls where ls = [v ! j | j <- [1..i-1], w ! j < w ! i] |
[/schedule]
3 Comentarios