Particiones por un elemento
Definir la función
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,
1 2 3 4 |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
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>
La primera es más eficiente que la segunda como se observa en el siguiente ejemplo