Número de parejas
Definir la función
|
1 |
nParejas :: Ord a => [a] -> Int |
tal que (nParejas xs) es el número de parejas de elementos iguales en xs. Por ejemplo,
|
1 2 3 4 |
nParejas [1,2,2,1,1,3,5,1,2] == 3 nParejas [1,2,1,2,1,3,2] == 2 nParejas [1..2*10^6] == 0 nParejas2 ([1..10^6] ++ [1..10^6]) == 1000000 |
En el primer ejemplos las parejas son (1,1), (1,1) y (2,2). En el segundo ejemplo, las parejas son (1,1) y (2,2).
Comprobar con QuickCheck que para toda lista de enteros xs, el número de parejas de xs es igual que el número de parejas de la inversa de xs.
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 |
import Test.QuickCheck import Data.List ((\\), group, sort) -- 1ª solución nParejas :: Ord a => [a] -> Int nParejas [] = 0 nParejas (x:xs) | x `elem` xs = 1 + nParejas (xs \\ [x]) | otherwise = nParejas xs -- 2ª solución nParejas2 :: Ord a => [a] -> Int nParejas2 xs = sum [length ys `div` 2 | ys <- group (sort xs)] -- 3ª solución nParejas3 :: Ord a => [a] -> Int nParejas3 = sum . map (`div` 2). map length . group . sort -- 4ª solución nParejas4 :: Ord a => [a] -> Int nParejas4 = sum . map ((`div` 2) . length) . group . sort -- Equivalencia prop_equiv :: [Int] -> Bool prop_equiv xs = nParejas xs == nParejas2 xs && nParejas xs == nParejas3 xs && nParejas xs == nParejas4 xs -- Comprobación: -- λ> quickCheck prop_equiv -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- λ> nParejas [1..20000] -- 0 -- (2.54 secs, 4,442,808 bytes) -- λ> nParejas2 [1..20000] -- 0 -- (0.03 secs, 12,942,232 bytes) -- λ> nParejas3 [1..20000] -- 0 -- (0.02 secs, 13,099,904 bytes) -- λ> nParejas4 [1..20000] -- 0 -- (0.01 secs, 11,951,992 bytes) -- Propiedad: prop_nParejas :: [Int] -> Bool prop_nParejas xs = nParejas xs == nParejas (reverse xs) -- Comprobación: -- λ> quickCheck prop_nParejas -- +++ OK, passed 100 tests. |
Pensamiento
Toda la imaginería
que no ha brotado del río,
barata bisutería.Antonio Machado