Máxima longitud de las sublistas comunes
Las sublistas comunes de «1325» y «36572» son «», «3»,»32″, «35», «2» y «5». El máximo de sus longitudes es 2.
Definir la función
|
1 |
maximo :: Eq a => [a] -> [a] -> Int |
tal que (maximo xs ys) es el máximo de las longitudes de las sublistas comunes de xs e ys. Por ejemplo,
|
1 2 3 |
maximo "1325" "36572" == 2 maximo [1,4..33] [2,4..33] == 5 maximo [1..10^6] [1..10^6] == 100000 |
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 |
import Data.List (subsequences, intersect) -- 1ª definición -- ============= maximo1 :: Eq a => [a] -> [a] -> Int maximo1 xs ys = maximum (map length (sublistasComunes xs ys)) -- (sublistasComunes xs ys) es la lista de las sublistas comunes de xs e -- ys. Por ejemplo, sublistasComunes :: Eq a => [a] -> [a] -> [[a]] sublistasComunes xs ys = subsequences xs `intersect` subsequences ys -- 2ª definición -- ============= maximo2 :: Eq a => [a] -> [a] -> Int maximo2 l1@(x:xs) l2@(y:ys) | x == y = 1 + maximo2 xs ys | otherwise = max (maximo2 xs l2) (maximo2 l1 ys) maximo2 _ _ = 0 -- Comparación de eficiencia -- ========================= -- λ> maximo1 [1,4..30] [2,4..30] -- 5 -- (3.60 secs, 0 bytes) -- λ> maximo2 [1,4..30] [2,4..30] -- 5 -- (1.58 secs, 216,347,472 bytes) -- -- λ> maximo2 [1..10^6] [1..10^6] -- 1000000 -- (2.44 secs, 407,051,096 bytes) |