Mayores sublistas crecientes
Definir la función
|
1 |
mayoresCrecientes :: Ord a => [a] -> [[a]] |
tal 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 9 10 |
λ> mayoresCrecientes [3,2,6,4,5,1] [[3,4,5],[2,4,5]] λ> mayoresCrecientes [3,2,3,2,3,1] [[2,3],[2,3],[2,3]] λ> 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^300)))) 10 |
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 |
import Data.List (subsequences) -- 1ª solución -- =========== 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ª solución -- =========== 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) |