Menu Close

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

   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. 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. 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. 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. 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.