import Data.List (genericLength)
import Data.Array
-- 1ª definición de descomposiciones (espacios de estado)
-- ======================================================
descomposiciones1 :: Integer -> [[Integer]]
descomposiciones1 n = busca [inicial]
where
busca [] = []
busca (e:es)
| esFinal n e = e : busca es
| otherwise = busca (es ++ sucesores n e)
-- Un estado es la lista de monedas usadas hasta ahora.
type Estado = [Integer]
-- inicial es el estado inicial del problema; es decir, cuando no se
-- ha usado ninguna moneda.
inicial :: Estado
inicial = []
-- (esFinal n e) es verifica si e es un estado final del problema n. Por
-- ejemplo,
-- esFinal (8,5,3) (4,4,0) == True
-- esFinal (8,5,3) (4,0,4) == False
esFinal :: Integer -> Estado -> Bool
esFinal n xs = sum xs == n
-- (sucesores n e) es la lista de los sucesores del estado e en el
-- problema n. Por ejemplo,
-- sucesores (8,5,3) (8,0,0) == [(3,5,0),(5,0,3)]
-- sucesores (8,5,3) (3,5,0) == [(0,5,3),(8,0,0),(3,2,3)]
sucesores :: Integer -> Estado -> [Estado]
sucesores n xs =
[1:xs | 1 + k <= n]
++ [3:xs | 3 + k <= n]
++ [4:xs | 4 + k <= n]
where k = sum xs
-- 2ª definición de descomposiciones (espacios de estado)
-- ======================================================
descomposiciones2 :: Integer -> [[Integer]]
descomposiciones2 n = busca [inicial2 n]
where
busca [] = []
busca (e:es)
| esFinal2 e = snd e : busca es
| otherwise = busca (es ++ sucesores2 n e)
-- Un estado es una par formado por la cantidad a conseguir y la lista
-- de monedas usadas hasta ahora.
type Estado2 = (Integer,[Integer])
-- (inicial2 n) es el estado inicial del problema; es decir, cuando no se
-- ha usado ninguna moneda.
inicial2 :: Integer -> Estado2
inicial2 n = (n,[])
-- (esFinal2 e) es verifica si e es un estado final del problema. Por
-- ejemplo,
-- esFinal (8,5,3) (4,4,0) == True
-- esFinal (8,5,3) (4,0,4) == False
esFinal2 :: Estado2 -> Bool
esFinal2 (k,_) = k == 0
-- (sucesores2 n e) es la lista de los sucesores del estado e en el
-- problema n. Por ejemplo,
-- sucesores (8,5,3) (8,0,0) == [(3,5,0),(5,0,3)]
-- sucesores (8,5,3) (3,5,0) == [(0,5,3),(8,0,0),(3,2,3)]
sucesores2 :: Integer -> Estado2 -> [Estado2]
sucesores2 n (k,xs) =
[(k-1, 1:xs) | k >= 1]
++ [(k-3, 3:xs) | k >= 3]
++ [(k-4, 4:xs) | k >= 4]
-- 3ª definición de descomposiciones
-- =================================
descomposiciones3 :: Integer -> [[Integer]]
descomposiciones3 0 = [[]]
descomposiciones3 1 = [[1]]
descomposiciones3 2 = [[1,1]]
descomposiciones3 3 = [[1,1,1],[3]]
descomposiciones3 n =
[1:xs | xs <- descomposiciones3 (n-1)]
++ [3:xs | xs <- descomposiciones3 (n-3)]
++ [4:xs | xs <- descomposiciones3 (n-4)]
-- 4ª definición de descomposiciones (dinámica)
-- ============================================
descomposiciones4 :: Integer -> [[Integer]]
descomposiciones4 n = v!n
where v = array (0,n) [(i,aux v i) | i <- [0..n]]
aux v 0 = [[]]
aux v 1 = [[1]]
aux v 2 = [[1,1]]
aux v 3 = [[1,1,1],[3]]
aux v k = map (1:) (v!(k-1))
++ map (3:) (v!(k-3))
++ map (4:) (v!(k-4))
-- 1ª definición de nDescomposiciones
-- ==================================
nDescomposiciones1 :: Integer -> Integer
nDescomposiciones1 =
genericLength . descomposiciones1
-- 2ª definición de nDescomposiciones
-- ==================================
nDescomposiciones2 :: Integer -> Integer
nDescomposiciones2 =
genericLength . descomposiciones2
-- 3ª definición de nDescomposiciones
-- ==================================
nDescomposiciones3 :: Integer -> Integer
nDescomposiciones3 =
genericLength . descomposiciones3
-- 4ª definición de nDescomposiciones
-- ==================================
nDescomposiciones4 :: Integer -> Integer
nDescomposiciones4 =
genericLength . descomposiciones4
-- 5ª definición de nDescomposiciones (dinámica)
-- =============================================
nDescomposiciones5 :: Integer -> Integer
nDescomposiciones5 n = v!n
where v = array (0,n) [(i,aux v i) | i <- [0..n]]
aux v 0 = 1
aux v 1 = 1
aux v 2 = 1
aux v 3 = 2
aux v k = v!(k-1) + v!(k-3) + v!(k-4)
-- Comparación de eficiencia
-- =========================
-- λ> nDescomposiciones1 20
-- 7921
-- (3.21 secs, 3,199,383,064 bytes)
-- λ> nDescomposiciones2 20
-- 7921
-- (3.17 secs, 3,176,666,880 bytes)
-- λ> nDescomposiciones3 20
-- 7921
-- (0.08 secs, 17,714,152 bytes)
--
-- λ> nDescomposiciones3 27
-- 229970
-- (3.73 secs, 628,730,968 bytes)
-- λ> nDescomposiciones4 27
-- 229970
-- (0.45 secs, 111,518,016 bytes)
--
-- λ> nDescomposiciones4 30
-- 974169
-- (2.02 secs, 454,484,992 bytes)
-- λ> nDescomposiciones5 30
-- 974169
-- (0.00 secs, 0 bytes)
-- λ> nDescomposiciones2 30
-- 974169
-- (2.10 secs, 441,965,208 bytes)
-- λ> nDescomposiciones3 30
-- 974169
-- (0.00 secs, 0 bytes)
--
-- λ> length (show (nDescomposiciones5 (10^5)))
-- 20899
-- (3.00 secs, 1,050,991,880 bytes) |
José A. Alonso