Número de ocurrencias de elementos
Definir la función
|
1 |
ocurrenciasElementos :: Ord a => [a] -> [(a,Int)] |
tal que (ocurrencias xs) es el conjunto de los elementos de xs junto con sus números de ocurrencias. Por ejemplo,
|
1 2 |
ocurrenciasElementos1 [3,2,3,1,2,3,5,3] == [(3,4),(2,2),(1,1),(5,1)] ocurrenciasElementos1 "tictac" == [('t',2),('i',1),('c',2),('a',1)] |
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 |
import Data.List (group, nub, sort) import Data.Maybe (fromJust) import qualified Data.Map as M import Test.QuickCheck -- 1ª solución -- =========== ocurrenciasElementos1 :: Ord a => [a] -> [(a,Int)] ocurrenciasElementos1 xs = [(x,ocurrencias x xs) | x <- nub xs] -- (ocurrencias x xs) es el número de ocurrencias de x en xs. Por -- ejemplo, -- ocurrencias 'a' "Salamanca" == 4 ocurrencias :: Ord a => a -> [a] -> Int ocurrencias x xs = length (filter (==x) xs) -- 2ª solución -- =========== ocurrenciasElementos2 :: Ord a => [a] -> [(a,Int)] ocurrenciasElementos2 xs = map ocurrencias (nub xs) where ocurrencias x = (x,fromJust (lookup x (frecuencias xs))) -- (frecuencias xs) es la lista ordenada de los elementos de xs juntos -- con sus números de ocurrencias. Por ejemplo, -- frecuencias [3,2,3,1,2,3,5,3] == [(1,1),(2,2),(3,4),(5,1)] frecuencias :: Ord a => [a] -> [(a, Int)] frecuencias xs = [(head ys, length ys) | ys <- group (sort xs)] -- 3ª solución -- =========== ocurrenciasElementos3 :: Ord a => [a] -> [(a,Int)] ocurrenciasElementos3 xs = map ocurrencias (nub xs) where diccionario = dicFrecuencias xs ocurrencias x = (x, diccionario M.! x) -- (dicFrecuencias xs) es el diccionario de los elementos de xs juntos -- con sus números de ocurrencias. Por ejemplo, -- λ> dicFrecuencias [3,2,3,1,2,3,5,3] -- fromList [(1,1),(2,2),(3,4),(5,1)] dicFrecuencias :: Ord a => [a] -> M.Map a Int dicFrecuencias xs = M.fromListWith (+) (zip xs (repeat 1)) -- 4ª solución -- =========== ocurrenciasElementos4 :: Ord a => [a] -> [(a,Int)] ocurrenciasElementos4 = foldl aux [] where aux [] y = [(y,1)] aux ((x,k):xs) y | x == y = (x, k + 1) : xs | otherwise = (x, k) : aux xs y -- Equivalencia de las definiciones -- ================================ -- La propiedad es prop_ocurrenciasElementos :: [Integer] -> Bool prop_ocurrenciasElementos xs = all (== (ocurrenciasElementos1 xs)) [f xs | f <- [ocurrenciasElementos2, ocurrenciasElementos3, ocurrenciasElementos4]] -- La comprobación es -- λ> quickCheck prop_ocurrenciasElementos -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> last (ocurrenciasElementos1 (show (product [1..10^5]))) -- ('5',42935) -- (7.93 secs, 11,325,169,512 bytes) -- λ> last (ocurrenciasElementos2 (show (product [1..10^5]))) -- ('5',42935) -- (8.46 secs, 11,750,911,592 bytes) -- λ> last (ocurrenciasElementos3 (show (product [1..10^5]))) -- ('5',42935) -- (8.29 secs, 11,447,015,896 bytes) -- λ> last (ocurrenciasElementos4 (show (product [1..10^5]))) -- ('5',42935) -- (9.97 secs, 12,129,527,912 bytes) |
El código se encuentra en GitHub.
Un comentario