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

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,

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

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)

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)

4 Comentarios

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

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

(MUY POCO EFICIENTE)

Responder

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

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

Responder

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

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

Responder

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
*/

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

Responder

Máxima longitud de las sublistas comunes

Soluciones

4 Comentarios

Leave a Reply to Chema CortésCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

4 Comentarios

Leave a Reply to Chema CortésCancel reply

Entradas recientes

Buscar

Correo electrónico