Listas obtenidas borrando k elementos
Definir la función
1 |
borra :: Int -> [a] -> [[a]] |
tal que (borra n xs) es la lista de las listas obtenidas borrando n elementos de xs. Por ejemplo,
1 2 3 4 5 6 7 8 |
borra 0 "abcd" == ["abcd"] borra 1 "abcd" == ["abc","abd","acd","bcd"] borra 2 "abcd" == ["ab","ac","ad","bc","bd","cd"] borra 3 "abcd" == ["a","b","c","d"] borra 4 "abcd" == [""] borra 5 "abcd" == [] borra 6 "abcd" == [] length (borra 2 [1..300]) == 44850 |
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 84 85 86 87 88 89 |
import Data.List (nub, subsequences) -- 1ª solución -- =========== borra1 :: Eq a => Int -> [a] -> [[a]] borra1 n xs = [ys | ys <- subsequences xs, length ys == k] where k = length xs - n -- 2ª solución -- =========== borra2 :: Eq a => Int -> [a] -> [[a]] borra2 0 xs = [xs] borra2 n [] = [] borra2 n (x:xs) = [x:ys | ys <- borra2 n xs] ++ borra2 (n-1) xs -- 3ª solución -- =========== borra3 :: Eq a => Int -> [a] -> [[a]] borra3 n xs = nub (itera n borraUnoListas [xs]) -- (borraUno xs) es la lista de listas obtenidas borrando un elemento de la -- lista no vacía xs de todas las formas posibles. Por ejemplo, -- borraUno "abcde" == ["bcde","acde","abde","abce","abcd"] borraUno :: [a] -> [[a]] borraUno [x] = [[]] borraUno (x:xs) = xs : map (x:) (borraUno xs) -- borraUnoListas ["abc", "def"] == ["bc","ac","ab","ef","df","de"] borraUnoListas :: [[a]] -> [[a]] borraUnoListas = concatMap borraUno -- (itera k f x) es el resultado de aplicar k veces la función f al -- elemento x. Por ejmplo, -- itera 3 (*2) 1 == 8 -- itera 4 (+2) 10 == 18 itera :: Eq a => Int -> (a -> a) -> a -> a itera 0 _ x = x itera n f x = itera (n-1) f (f x) -- 2ª definición de itera itera2 :: Eq a => Int -> (a -> a) -> a -> a itera2 0 _ = id itera2 n f = itera2 (n-1) f . f -- 3ª definición de itera itera3 :: Eq a => Int -> (a -> a) -> a -> a itera3 n f x = (iterate f x) !! n -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (borra1 10 [1..11]) -- 11 -- (0.03 secs, 527,712 bytes) -- λ> length (borra2 10 [1..11]) -- 11 -- (0.01 secs, 917,720 bytes) -- λ> length (borra3 10 [1..11]) -- 11 -- (22.32 secs, 20,104,455,496 bytes) -- -- λ> length (borra1 25 [1..26]) -- 26 -- (16.30 secs, 13,958,748,280 bytes) -- λ> length (borra2 25 [1..26]) -- 26 -- (36.36 secs, 25,769,904,744 bytes) -- -- λ> length (borra1 2 [1..26]) -- 325 -- (16.51 secs, 13,958,767,696 bytes) -- λ> length (borra2 2 [1..26]) -- 325 -- (0.01 secs, 168,272 bytes) -- λ> length (borra3 2 [1..26]) -- 325 -- (0.03 secs, 1,209,992 bytes) -- -- λ> length (borra2 2 [1..100]) -- 4950 -- (0.06 secs, 59,128,272 bytes) -- λ> length (borra3 2 [1..100]) -- 4950 -- (6.37 secs, 57,943,128 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>