Inversiones de un número
Un número tiene una inversión cuando existe un dígito x a la derecha de otro dígito de forma que x es menor que y. Por ejemplo, en el número 1745 hay dos inversiones ya que 4 es menor que 7 y 5 es menor que 7 y están a la derecha de 7.
Definir la función
|
1 |
nInversiones :: Integer -> Int |
tal que (nInversiones n) es el número de inversiones de n. Por ejemplo,
|
1 |
nInversiones 1745 == 2 |
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 |
import Data.List (tails) -- 1ª definición -- ============= nInversiones1 :: Integer -> Int nInversiones1 = length . inversiones . show -- (inversiones xs) es la lista de las inversiones de xs. Por ejemplo, -- inversiones "1745" == [('7','4'),('7','5')] -- inversiones "cbafd" == [('c','b'),('c','a'),('b','a'),('f','d')] inversiones :: Ord a => [a] -> [(a,a)] inversiones [] = [] inversiones (x:xs) = [(x,y) | y <- xs, y < x] ++ inversiones xs -- 2ª definición -- ============= nInversiones2 :: Integer -> Int nInversiones2 = aux . show where aux [] = 0 aux (y:ys) | null xs = aux ys | otherwise = length xs + aux ys where xs = [x | x <- ys, x < y] -- 3ª solución -- =========== nInversiones3 :: Integer -> Int nInversiones3 x = sum $ map f xss where xss = init $ tails (show x) f (x:xs) = length $ filter (<x) xs -- Comparación de eficiencia -- ========================= -- La comparación es -- ghci> let f1000 = product [1..1000] -- ghci> nInversiones1 f1000 -- 1751225 -- (2.81 secs, 452526504 bytes) -- ghci> nInversiones2 f1000 -- 1751225 -- (2.45 secs, 312752672 bytes) -- ghci> nInversiones3 f1000 -- 1751225 -- (0.71 secs, 100315896 bytes) |