| Copyright | Exercitium |
|---|---|
| License | GPL-3 |
| Maintainer | JoseA.Alonso@gmail.com |
| Safe Haskell | Safe |
| Language | Haskell2010 |
Numero_de_inversiones
Description
Número de inversiones
Se dice que en una sucesión de números x(1), x(2), ..., x(n) hay una inversión cuando existe un par de números x(i) > x(j), siendo i < j. Por ejemplo, en la permutación 2, 1, 4, 3 hay dos inversiones (2 antes que 1 y 4 antes que 3) y en la permutación 4, 3, 1, 2 hay cinco inversiones (4 antes 3, 4 antes 1, 4 antes 2, 3 antes 1, 3 antes 2).
Definir la función
numeroInversiones :: Ord a => [a] -> Int
tal que (numeroInversiones xs) es el número de inversiones de xs. Por ejemplo,
>>>numeroInversiones [2,1,4,3]2>>>numeroInversiones [4,3,1,2]5
- numeroInversiones :: Ord a => [a] -> Int
- numeroInversiones2 :: Ord a => [a] -> Int
- numeroInversiones3 :: Ord a => [a] -> Int
- numeroInversiones4 :: Ord a => [a] -> Int
- prop_equiv_numeroInversiones :: [Int] -> Bool
- verifica_equiv_numeroInversiones :: IO ()
Documentation
numeroInversiones :: Ord a => [a] -> Int Source #
1ª solución (por recursión y compresión).
numeroInversiones3 :: Ord a => [a] -> Int Source #
3ª solución (por comprensión)
numeroInversiones4 :: Ord a => [a] -> Int Source #
4ª solución (con vectores)
prop_equiv_numeroInversiones :: [Int] -> Bool Source #
(prop_equiv_numeroInversiones xs) se verifica si las
definiciones de numeroInversiones son equivalentes sobre xs. Por
ejemplo,
>>>all prop_equiv_numeroInversiones [[2,1,4,3], [4,3,1,2]]True
verifica_equiv_numeroInversiones :: IO () Source #
Comprueba la equivalencia de las definiciones de
numeroInversiones.
>>>verifica_equiv_numeroInversiones+++ OK, passed 100 tests.
Comparación de eficiencia
> numeroInversiones [2000,1999..1] 1999000 (1.94 secs, 257,172,224 bytes) > numeroInversiones2 [2000,1999..1] 1999000 (0.20 secs, 113,228,368 bytes) > numeroInversiones3 [2000,1999..1] 1999000 (27.40 secs, 672,913,536 bytes) > numeroInversiones4 [2000,1999..1] 1999000 (4.18 secs, 832,705,200 bytes)