Segmentos comunes maximales

PorJosé A. Alonso 30-diciembre-20167-enero-2017

Los segmentos de «abcd» son

   ["","a","ab","abc","abcd","b","bc","bcd","c","cd","d"]

1	["","a","ab","abc","abcd","b","bc","bcd","c","cd","d"]

Los segmentos comunes de «abcd» y «axbce» son

   ["","a","b","bc","c"]

1	["","a","b","bc","c"]

Los segmentos comunes maximales (es decir, no contenidos en otros segmentos) de «abcd» y «axbce» son

   ["a","bc"]

1	["a","bc"]

Definir la función

   segmentosComunesMaximales :: Eq a => [a] -> [a] -> [[a]]

1	segmentosComunesMaximales :: Eq a => [a] -> [a] -> [[a]]

tal que (segmentosComunesMaximales xs ys) es la lista de los segmentos comunes maximales de xs e ys. Por ejemplo,

   segmentosComunesMaximales "abcd" "axbce"  ==  ["a","bc"]
   segmentosComunesMaximales [8,8] [8]       ==  [[8]]

1 2	segmentosComunesMaximales "abcd" "axbce" == ["a","bc"] segmentosComunesMaximales [8,8] [8] == [[8]]

Soluciones

import Data.List (inits, tails, isInfixOf)

segmentosComunesMaximales :: Eq a => [a] -> [a] -> [[a]]
segmentosComunesMaximales xs ys =
  nub [zs | zs <- zss
          , null [us | us <- zss, zs `isInfixOf` us, us /= zs]]
  where zss = segmentosComunes xs ys

segmentosComunes :: Eq a => [a] -> [a] -> [[a]]
segmentosComunes xs ys =
  [zs | zs <- segmentos xs
      , zs `isInfixOf` ys]

-- (segmentos xs) es la lista de los segmentos de xs. Por ejemplo,
--    segmentos "abc"  ==  ["","a","ab","abc","b","bc","c"]
segmentos :: [a] -> [[a]]
segmentos xs =
  [] : concatMap (tail . inits) (init (tails xs))

import Data.List (inits, tails, isInfixOf)

segmentosComunesMaximales :: Eq a => [a] -> [a] -> [[a]]

segmentosComunesMaximales xs ys =

nub [zs | zs <- zss

, null [us | us <- zss, zs `isInfixOf` us, us /= zs]]

where zss = segmentosComunes xs ys

segmentosComunes :: Eq a => [a] -> [a] -> [[a]]

segmentosComunes xs ys =

[zs | zs <- segmentos xs

, zs `isInfixOf` ys]

-- (segmentos xs) es la lista de los segmentos de xs. Por ejemplo,

-- segmentos "abc" == ["","a","ab","abc","b","bc","c"]

segmentos :: [a] -> [[a]]

segmentos xs =

[] : concatMap (tail . inits) (init (tails xs))

7 Comentarios

segmentos :: [a] -> [[a]]
segmentos []     = [[]]
segmentos (x:xs) = [x: yss | yss <- inits xs] ++ segmentos xs 

segmentosComunes :: Eq a => [a] -> [a] -> [[a]]
segmentosComunes xs ys =
  intersect (segmentos xs) (segmentos ys)

segmentosComunesMaximales :: Eq a => [a] -> [a] -> [[a]]
segmentosComunesMaximales xs ys =
  reverse (aux1 (segmentosComunes xs ys) [])
  where
    aux1 [] zs = zs 
    aux1 (t:ts) zs
      | any (isInfixOf t) (delete t (segmentosComunes xs ys)) = aux1 ts zs
      | otherwise = aux1 ts (t:zs)

segmentos :: [a] -> [[a]]

segmentos [] = [[]]

segmentos (x:xs) = [x: yss | yss <- inits xs] ++ segmentos xs

segmentosComunes :: Eq a => [a] -> [a] -> [[a]]

segmentosComunes xs ys =

intersect (segmentos xs) (segmentos ys)

segmentosComunesMaximales :: Eq a => [a] -> [a] -> [[a]]

segmentosComunesMaximales xs ys =

reverse (aux1 (segmentosComunes xs ys) [])

where

aux1 [] zs = zs

aux1 (t:ts) zs

| any (isInfixOf t) (delete t (segmentosComunes xs ys)) = aux1 ts zs

| otherwise = aux1 ts (t:zs)

Responder

import Data.List

segmentos' :: Eq a => [a] -> [[a]]
segmentos' []       = []
segmentos' a@(x:xs) = inits a ++ segmentos' xs

segmentosA2 :: Eq a => [a] -> [[a]]
segmentosA2 = nub . segmentos'

contiene :: Eq a => [a] -> [a] -> Bool
contiene xs ys = and [x `elem` ys | x <- xs]

elemento :: Eq a => [a] -> [[a]] -> Bool
elemento xs []       = False
elemento xs (ys:xss) = xs `isPrefixOf` ys  || elemento xs xss

segmentosComunesA2 :: Eq a => [a] -> [a] -> [[a]]
segmentosComunesA2 xs ys = [a | a <- segmentosA2 xs
                              , a `elemento` segmentosA2 ys]
  
segmentosComunesMaximalesA2 :: Eq a => [a] -> [a] -> [[a]]
segmentosComunesMaximalesA2 xs ys =
  [a | a <- zs
     , all (==False) [a `contiene` b | b <- zs \\ [a]] ]
  where zs = segmentosComunesA2 xs ys

import Data.List

segmentos' :: Eq a => [a] -> [[a]]

segmentos' [] = []

segmentos' a@(x:xs) = inits a ++ segmentos' xs

segmentosA2 :: Eq a => [a] -> [[a]]

segmentosA2 = nub . segmentos'

contiene :: Eq a => [a] -> [a] -> Bool

contiene xs ys = and [x `elem` ys | x <- xs]

elemento :: Eq a => [a] -> [[a]] -> Bool

elemento xs [] = False

elemento xs (ys:xss) = xs `isPrefixOf` ys || elemento xs xss

segmentosComunesA2 :: Eq a => [a] -> [a] -> [[a]]

segmentosComunesA2 xs ys = [a | a <- segmentosA2 xs

, a `elemento` segmentosA2 ys]

segmentosComunesMaximalesA2 :: Eq a => [a] -> [a] -> [[a]]

segmentosComunesMaximalesA2 xs ys =

[a | a <- zs

, all (==False) [a `contiene` b | b <- zs \\ [a]] ]

where zs = segmentosComunesA2 xs ys

Responder

segmentosComunesMaximales :: Eq a => [a] -> [a] -> [[a]]
segmentosComunesMaximales xs ys = nub (vacio (auxL xs ys []))
  where auxL [] ys v | null v    = []
                     | otherwise = [v]
        auxL (x:xs) ys v
          | isInfixOf (v ++ [x]) ys = auxL xs ys (v++[x])
          | null v                  = auxL xs ys []
          | otherwise               = v:auxL (x:xs) ys []
        vacio xs | null xs   = [[]]
                 | otherwise = xs

segmentosComunesMaximales :: Eq a => [a] -> [a] -> [[a]]

segmentosComunesMaximales xs ys = nub (vacio (auxL xs ys []))

where auxL [] ys v | null v = []

| otherwise = [v]

auxL (x:xs) ys v

| isInfixOf (v ++ [x]) ys = auxL xs ys (v++[x])

| null v = auxL xs ys []

| otherwise = v:auxL (x:xs) ys []

vacio xs | null xs = [[]]

| otherwise = xs

Responder

import Data.List

segmentosComunesMaximales :: Eq a => [a] -> [a] -> [[a]]
segmentosComunesMaximales = (maximales.) . segmentosComunes

segmentos :: [a] -> [[a]]
segmentos [] = []
segmentos xs = inits xs ++ segmentos (tail xs)

segmentosComunes :: Eq a => [a] -> [a] -> [[a]]
segmentosComunes xs ys = filter (`isInfixOf` ys) (segmentos xs)

maximales :: Eq a => [[a]] -> [[a]]
maximales xss = [xs | xs <- xss
                    , not $ any (xs `isInfixOf`) (delete xs xss) ]

import Data.List

segmentosComunesMaximales :: Eq a => [a] -> [a] -> [[a]]

segmentosComunesMaximales = (maximales.) . segmentosComunes

segmentos :: [a] -> [[a]]

segmentos [] = []

segmentos xs = inits xs ++ segmentos (tail xs)

segmentosComunes :: Eq a => [a] -> [a] -> [[a]]

segmentosComunes xs ys = filter (`isInfixOf` ys) (segmentos xs)

maximales :: Eq a => [[a]] -> [[a]]

maximales xss = [xs | xs <- xss

, not $ any (xs `isInfixOf`) (delete xs xss) ]

Responder

import Data.List

segmentosComunesMaximales :: Eq a => [a] -> [a] -> [[a]]
segmentosComunesMaximales = (maximales . ) . segmentosComunes

segmentos :: Eq a => [a] -> [[a]]
segmentos = nub . concatMap inits . tails

segmentosComunes :: Eq a => [a] -> [a] -> [[a]]
segmentosComunes xs = filter (`isInfixOf` xs) . segmentos

maximales :: Eq a => [[a]] -> [[a]]
maximales xss = [ xs | xs <- xss, maximal xs xss]

maximal :: Eq a => [a] -> [[a]] -> Bool
maximal xs =  all (not . (xs `isInfixOf`)) . delete xs

import Data.List

segmentosComunesMaximales :: Eq a => [a] -> [a] -> [[a]]

segmentosComunesMaximales = (maximales . ) . segmentosComunes

segmentos :: Eq a => [a] -> [[a]]

segmentos = nub . concatMap inits . tails

segmentosComunes :: Eq a => [a] -> [a] -> [[a]]

segmentosComunes xs = filter (`isInfixOf` xs) . segmentos

maximales :: Eq a => [[a]] -> [[a]]

maximales xss = [ xs | xs <- xss, maximal xs xss]

maximal :: Eq a => [a] -> [[a]] -> Bool

maximal xs = all (not . (xs `isInfixOf`)) . delete xs

Responder

import Data.List

segmentos :: [a] -> [[a]]
segmentos []     = []
segmentos (x:xs) = tails (reverse (x:xs)) ++ segmentos xs

segmentos2 xs = nub [reverse xs | xs <- segmentos xs]

comun xs ys = intersect (segmentos2 xs )(segmentos2 ys)

segmentosComunesMaximales xs ys =
  nub [ts | ts <- comun xs ys
          , and [nocontenido ts (segmentos ps) | ps <- comun xs ys
                                                 , ps /= ts]]

nocontenido xs yss =
  and [not (elem xs (segmentos ps)) | ps <- yss]

import Data.List

segmentos :: [a] -> [[a]]

segmentos [] = []

segmentos (x:xs) = tails (reverse (x:xs)) ++ segmentos xs

segmentos2 xs = nub [reverse xs | xs <- segmentos xs]

comun xs ys = intersect (segmentos2 xs )(segmentos2 ys)

segmentosComunesMaximales xs ys =

nub [ts | ts <- comun xs ys

, and [nocontenido ts (segmentos ps) | ps <- comun xs ys

, ps /= ts]]

nocontenido xs yss =

and [not (elem xs (segmentos ps)) | ps <- yss]

Responder

segmentos :: Eq a => [a] -> [[a]]
segmentos [] = [[]]
segmentos (x:xs) = nub (inits (x:xs) ++ segmentos xs)

segmentosComunes :: Eq a => [a] -> [a] -> [[a]]
segmentosComunes xs ys = intersect (segmentos xs) (segmentos ys)

segmentosComunesMaximales :: Eq a => [a] -> [a] -> [[a]]
segmentosComunesMaximales xs ys
  | xs == ys = [xs]
  | otherwise = maximales (segmentosComunes xs ys)

maximales :: Eq a => [[a]] -> [[a]]                               
maximales xss = quitaRepetidos (concat (map segmentos xss))

quitaRepetidos :: Eq a => [[a]] -> [[a]]
quitaRepetidos [] = []
quitaRepetidos (x:xs)
  | elem x xs = quitaRepetidos (filter (/=x) (x:xs))
  | otherwise = x : quitaRepetidos xs

segmentos :: Eq a => [a] -> [[a]]

segmentos [] = [[]]

segmentos (x:xs) = nub (inits (x:xs) ++ segmentos xs)

segmentosComunes :: Eq a => [a] -> [a] -> [[a]]

segmentosComunes xs ys = intersect (segmentos xs) (segmentos ys)

segmentosComunesMaximales :: Eq a => [a] -> [a] -> [[a]]

segmentosComunesMaximales xs ys

| xs == ys = [xs]

| otherwise = maximales (segmentosComunes xs ys)

maximales :: Eq a => [[a]] -> [[a]]

maximales xss = quitaRepetidos (concat (map segmentos xss))

quitaRepetidos :: Eq a => [[a]] -> [[a]]

quitaRepetidos [] = []

quitaRepetidos (x:xs)

| elem x xs = quitaRepetidos (filter (/=x) (x:xs))

| otherwise = x : quitaRepetidos xs

Responder

Segmentos comunes maximales

Soluciones

7 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

7 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico