Limitación del número de repeticiones
Definir la función
1 |
conRepeticionesAcotadas :: Eq a => [a] -> Int -> [a] |
tal que (conRepeticionesAcotadas xs n) es una lista que contiene cada elemento de xs como máximo n veces sin reordenar (se supone que n es un número positivo).. Por ejemplo,
1 2 3 4 |
conRepeticionesAcotadas [1,2,3,1,2,1,3,2,3,5] 1 == [1,2,3,5] conRepeticionesAcotadas [1,2,3,1,2,1,3,2,3,5] 2 == [1,2,3,1,2,3,5] conRepeticionesAcotadas [1,2,3,1,2,1,3,2,3,5] 3 == [1,2,3,1,2,1,3,2,3,5] conRepeticionesAcotadas [1,2,3,1,2,1,3,2,3,5] 4 == [1,2,3,1,2,1,3,2,3,5] |
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 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
import Data.List (foldl') import Data.Maybe (fromJust, isNothing) import Test.QuickCheck (Property, (==>),quickCheck) -- 1ª solución -- =========== conRepeticionesAcotadas :: Eq a => [a] -> Int -> [a] conRepeticionesAcotadas xs n = reverse (aux [] xs) where aux zs [] = zs aux zs (y:ys) | m < n = aux (y:zs) ys | otherwise = aux zs ys where m = nOcurrencias y zs -- (nOcurrencias x ys) es el número de ocurrencias de x en ys. Por -- ejemplo, -- nOcurrencias 7 [7,2,7,7,5] == 3 nOcurrencias :: Eq a => a -> [a] -> Int nOcurrencias x ys = length (filter (== x) ys) -- Se puede simplificar la definición de nOcurrencias: nOcurrencias2 :: Eq a => a -> [a] -> Int nOcurrencias2 x = length . filter (== x) -- 2ª solución -- =========== conRepeticionesAcotadas2 :: Eq a => [a] -> Int -> [a] conRepeticionesAcotadas2 xs n = reverse (foldl' aux [] xs) where aux zs y | m < n = y:zs | otherwise = zs where m = nOcurrencias y zs -- 3ª solución -- =========== conRepeticionesAcotadas3 :: Eq a => [a] -> Int -> [a] conRepeticionesAcotadas3 xs n = reverse (aux [] [] xs) where aux as _ [] = as aux as bs (y:ys) | y `elem` bs = aux as bs ys | m < n = aux (y:as) bs ys | otherwise = aux as (y:bs) ys where m = nOcurrencias y as -- 4ª solución -- =========== conRepeticionesAcotadas4 :: Eq a => [a] -> Int -> [a] conRepeticionesAcotadas4 xs n = aux xs [] where aux [] _ = [] aux (y:ys) ps | r == Nothing = y : aux ys ((y,1) : ps) | m < n = y : aux ys ((y,m+1) : ps) | otherwise = aux ys ps where r = busca y ps Just m = r -- (busca x ps) es justamente la segunda componente del primer par de ps -- cuya primera componente es xs, si ps tiene algún par cuya primera -- componente es x; y Nothing en caso contrario. Por ejemplo, -- busca 'a' [('b',2),('a',3),('a',1)] == Just 3 -- busca 'c' [('b',2),('a',3),('a',1)] == Nothing busca :: Eq a => a -> [(a,b)] -> Maybe b busca x ps | null ys = Nothing | otherwise = Just (head ys) where ys = [n | (y,n) <- ps, y == x] -- 5ª solución -- =========== conRepeticionesAcotadas5 :: Eq a => [a] -> Int -> [a] conRepeticionesAcotadas5 xs n = aux xs [] where aux [] _ = [] aux (y:ys) ps | isNothing r = y : aux ys ((y,1) : ps) | m < n = y : aux ys ((y,m+1) : ps) | otherwise = aux ys ps where r = lookup y ps m = fromJust r -- Equivalencia de las definiciones -- ================================ -- La propiedad es prop_conRepeticionesAcotadas :: [Int] -> Int -> Property prop_conRepeticionesAcotadas xs n = n > 0 ==> all (==(conRepeticionesAcotadas xs n)) [ conRepeticionesAcotadas2 xs n , conRepeticionesAcotadas3 xs n , conRepeticionesAcotadas4 xs n , conRepeticionesAcotadas5 xs n] -- La comprobación es -- λ> quickCheck prop_conRepeticionesAcotadas -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (conRepeticionesAcotadas (concat [[1..n] | n <- [1..500]]) 2) -- 999 -- (5.14 secs, 64,372,768 bytes) -- λ> length (conRepeticionesAcotadas2 (concat [[1..n] | n <- [1..500]]) 2) -- 999 -- (4.95 secs, 62,322,880 bytes) -- λ> length (conRepeticionesAcotadas3 (concat [[1..n] | n <- [1..500]]) 2) -- 999 -- (0.38 secs, 38,764,952 bytes) -- λ> length (conRepeticionesAcotadas4 (concat [[1..n] | n <- [1..500]]) 2) -- 999 -- (5.66 secs, 2,429,904,144 bytes) -- λ> length (conRepeticionesAcotadas5 (concat [[1..n] | n <- [1..500]]) 2) -- 999 -- (0.68 secs, 48,536,872 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