Menu Close

Máxima longitud de las sublistas comunes

José A. Alonso,

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

   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,

   maximo "1325" "36572"       == 2
   maximo [1,4..33] [2,4..33]  == 5
   maximo [1..10^6] [1..10^6]  == 100000

Soluciones

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)
Medio
, , , , ,

4 soluciones de “Máxima longitud de las sublistas comunes”

  1. Responder
    paocabper 
    comunes xs ys = [z|z<-(subsequences xs), z`elem`(subsequences ys)]
maximo xs ys = maximum [length zs|zs <- (comunes xs ys)]

    (MUY POCO EFICIENTE)

  2. Responder
    Chema Cortés 
    maximo :: Eq a => [a] -> [a] -> Int
maximo [] _ = 0
maximo _ [] = 0
maximo (x:xs) (y:ys) | x == y    = 1 + maximo xs ys
                     | otherwise = max (maximo (x:xs) ys)
                                       (maximo xs (y:ys))
  3. Responder
    Chema Cortés

    Una mejora de mi anterior versión:

    maximo :: Eq a => [a] -> [a] -> Int
maximo [] _          = 0
maximo _ []          = 0
maximo (x:xs) (y:ys) | x == y    = 1 + maximo xs ys
                     | otherwise = maximum [
                           maximo (x:xs) ys',
                           maximo xs' (y:ys),
                           maximo xs ys
                        ]
    where xs' = dropWhile (/=y) xs
          ys' = dropWhile (/=x) ys
  4. Responder
    Alejandro

    En Maxima

    maximo (xs,ys) := block (
  if emptyp (xs)
      then 0
  elseif emptyp (ys)
      then 0
  elseif is (first(xs) = first(ys))
      then 1 + maximo (rest(xs),rest(ys))
  else
      max (maximo(xs,rest(ys)), maximo(rest(xs),ys)))$
 
/* Ejemplo:
   (%i1) maximo ([1,3,2,5], [3,6,5,7,2]);
   (%o1) 2
*/

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.