Particiones por un elemento

Definir la función

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

1	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")]

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)

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>

4 Comentarios

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

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

Responder

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)

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

Responder

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

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

Responder

particiones :: Eq a => [a] -> a -> [([a],[a])]
particiones xs y = [(take i xs, drop i xs) | (x,i) <- zip xs [0..], x == y]

1 2	particiones :: Eq a => [a] -> a -> [([a],[a])] particiones xs y = [(take i xs, drop i xs) \| (x,i) <- zip xs [0..], x == y]

Responder

Particiones por un elemento

Soluciones

Nuevas soluciones

4 Comentarios

Leave a Reply to José A. AlonsoCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Nuevas soluciones

Se puede imprimir o compartir con

4 Comentarios

Leave a Reply to José A. AlonsoCancel reply

Entradas recientes

Buscar

Correo electrónico