Menu Close

Particiones por un elemento

Definir la función

   particiones :: Eq a => [a] -> a -> [([a],[a])]

tal que (particiones xs y) es la lista de las particiones de xs en dos partes tales que el primer elemento de la segunda parte es y. Por ejemplo,

   particiones [2,9,1,3,9,4] 9   == [([2],[9,1,3,9,4]),([2,9,1,3],[9,4])]
   particiones [2,9,1,3,9,4] 3   == [([2,9,1],[3,9,4])]
   particiones [2,9,1,3,9,4] 7   == []
   particiones "Particiones" 'i' == [("Part","iciones"),("Partic","iones")]

Soluciones

import Data.List (tails, inits)
 
-- 1ª solución
-- ===========
 
particiones :: Eq a => [a] -> a -> [([a],[a])]
particiones [] _ = []
particiones xs y
  | null vs = []
  | otherwise = (us,vs) : [(us ++ y:us', vs')
                          | (us',vs') <- particiones (tail vs) y ]
  where (us,vs) = span (/=y) xs
 
-- 2ª solución
-- ===========
 
particiones2 :: Eq a => [a] -> a -> [([a],[a])]
particiones2 xs y =
  [(ys,z:zs) | (ys,z:zs) <- listaPares xs, z == y]
 
-- (listaPares xs) es la lista de los pares que resultan al dividir la
-- lista xs en dos partes. Por ejemplo,
--    λ> listaPares [2,9,1,3,9,4]
--    [([],[2,9,1,3,9,4]),([2],[9,1,3,9,4]),([2,9],[1,3,9,4]),([2,9,1],[3,9,4]),
--    ([2,9,1,3],[9,4]),([2,9,1,3,9],[4])]
listaPares :: [a] -> [([a],[a])]
listaPares xs = init (zip (inits xs) (tails xs))
 
-- 3ª solución
-- ===========
 
particiones3 :: Eq a => [a] -> a -> [([a],[a])]
particiones3 xs y =
  [(prefijoSufijo xs zs,zs) | zs <- sufijos xs y]
 
-- (sufijos xs y) es la lista de los sufijos de xs que empiezan por
-- y. Por ejemplo,
--   λ> sufijos "particiones" 'i'
--   ["iciones","iones"]
sufijos :: Eq a => [a] -> a -> [[a]]
sufijos xs y = filter ((== y) . head) (init (tails xs))
 
-- (prefijoSufijo xs zs) es el prefijo de xs que junto con el sufijo zs
-- forma la lista xs. Por ejemplo,
--   λ> prefijoSufijo "particiones" "iciones"
--   "part"
prefijoSufijo :: [a] -> [a] -> [a]
prefijoSufijo xs zs = (inits xs) !! (length xs - length zs)
 
-- Comprobación de la equivalencia
-- ===============================
 
-- La propiedad es
prop_equivalencia :: [Int] -> Int -> Bool
prop_equivalencia xs y =
  particiones xs y'  == particiones2 xs y' &&
  particiones2 xs y' == particiones3 xs y'
  where y' = y `mod` length xs
 
-- La comprobación es
--    λ> quickCheck prop_equivalencia
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> length (particiones (take (10^5) (cycle [1..9])) 5)
--    11111
--    (9.10 secs, 13,375,324,416 bytes)
--    λ> length (particiones2 (take (10^5) (cycle [1..9])) 5)
--    11111
--    (0.08 secs, 44,107,672 bytes)
--    λ> length (particiones3 (take (10^5) (cycle [1..9])) 5)
--    11111
--    (0.07 secs, 21,524,936 bytes)
--
--    λ> length (particiones2 (take (10^7) (cycle [1..9])) 5)
--    1111111
--    (3.93 secs, 4,400,105,800 bytes)
--    λ> length (particiones3 (take (10^7) (cycle [1..9])) 5)
--    1111111
--    (1.88 secs, 2,142,328,800 bytes)

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
Medio

4 soluciones de “Particiones por un elemento

  1. Rubén Muñoz Mkrtchian
    import Data.List (tails, inits)
     
    particiones :: Eq a => [a] -> a -> [([a],[a])]
    particiones xs y = [(primerPar xs zs2,zs2) | zs2 <- segundosPares xs y]
     
    -- segundosPares xs y es la lista formada por los segundos pares de particiones
    -- xs y, verificando que el primer elemento de dichos elementos es y. Por
    -- ejemplo,
    --   λ> segundosPares "particiones" 'i'
    --   ["iciones","iones"]
     
    segundosPares :: Eq a => [a] -> a -> [[a]]
    segundosPares xs y = filter ((== y) . head) (init (tails xs))
     
    -- Una vez conocemos las listas que ocupan la segunda posición de cada par,
    -- observamos lo siguiente. Sabiendo que la suma de longitudes de los dos
    -- elementos de cada par suman la longitud de xs, podemos hallar el primer
    -- elemento de dicho par a partir de cada uno de los segundos elementos.
    -- Definimos por lo tanto la función primerPar xs zs. Por ejemplo,
    --   λ> primerPar "particiones" "iciones"
    --   "part"
     
    primerPar :: [a] -> [a] -> [a]
    primerPar xs zs = (inits xs) !! (length xs - length zs)
     
    -- Esta segunda definición es más simple y, aunque no se note mucho, también es
    -- un poco más eficiente.
     
    particiones2 :: Eq a => [a] -> a -> [([a],[a])]
    particiones2 xs y = [par | par <- listaPares xs, head (snd par) == y]
     
    -- listaPares xs es la lista formada por todos los posibles pares que resultan
    -- al dividir la lista xs en dos partes. Por ejemplo,
    --    λ> listaPares [2,9,1,3,9,4]
    --    [([],[2,9,1,3,9,4]),([2],[9,1,3,9,4]),([2,9],[1,3,9,4]),([2,9,1],[3,9,4]),
    --    ([2,9,1,3],[9,4]),([2,9,1,3,9],[4])]
     
    listaPares :: [a] -> [([a],[a])]
    listaPares xs = init (zip (inits xs) (tails xs))
    • José A. Alonso

      La primera es más eficiente que la segunda como se observa en el siguiente ejemplo

      λ> length (particiones (take (10^7) (cycle [1..9])) 5)
      1111111
      (1.88 secs, 2,142,328,032 bytes)
      λ> length (particiones2 (take (10^7) (cycle [1..9])) 5)
      1111111
      (4.78 secs, 5,120,104,768 bytes)
  2. Mercedes Vega Gallo
    particiones :: Eq a => [a] -> a -> [([a],[a])]
    particiones xs y = aux xs (posicion xs y)
                        where aux xs [] = []
                              aux xs (z:zs) = (take (z-1) xs,drop (z-1) xs):aux xs zs
     
                              posicion xs y = map q (filter p (zip xs [1..]))
                                    where p (a,b) = a==y
                                          q (a,b) = b
  3. María Ruiz
    particiones :: Eq a => [a] -> a -> [([a],[a])]
    particiones xs y = [(take i xs, drop i xs) | (x,i) <- zip xs [0..], x == y]

Leave a Reply

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