Inversiones de un número

José A. Alonso

25-05-2015

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

nInversiones :: Integer -> Int

tal que (nInversiones n) es el número de inversiones de n. Por ejemplo,

nInversiones 1745  ==  2

Soluciones

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
--    λ> let f1000 = product [1..1000]
--    λ> nInversiones1 f1000
--    1751225
--    (2.81 secs, 452526504 bytes)
--    λ> nInversiones2 f1000
--    1751225
--    (2.45 secs, 312752672 bytes)
--    λ> nInversiones3 f1000
--    1751225
--    (0.71 secs, 100315896 bytes)