# Día: 5 febrero, 2021

## Listas obtenidas borrando k elementos

Definir la función

` borra :: Int -> [a] -> [[a]]`

tal que (borra n xs) es la lista de las listas obtenidas borrando n elementos de xs. Por ejemplo,

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

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