Listas con los ceros emparejados
Sea S un conjunto de números. Las listas de ceros emparejados de S son las listas formadas con los elementos de S y en las cuales los ceros aparecen en sublistas de longitud par. Por ejemplo, si S = {0,1,2} entonces [1], [2], [2,1], [2,0,0,2,0,0,1] y [0,0,0,0,1,2] son listas de ceros emparejados de S; pero [0,0,0,2,1,0,0] y [0,0,1,0,1] no lo son.
Definir las funciones
|
1 2 |
cerosEmparejados :: Integer -> Integer -> [[Integer]] nCerosEmparejados :: Integer -> Integer -> Integer |
tales que
+ (cerosEmparejados m n) es la lista de las listas de longitud n de ceros emparejados con los números 0, 1, 2,…, m. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
ghci> cerosEmparejados 2 0 [[]] ghci> cerosEmparejados 2 1 [[1],[2]] ghci> cerosEmparejados 3 1 [[1],[2],[3]] ghci> cerosEmparejados 2 2 [[1,1],[1,2],[2,1],[2,2],[0,0]] ghci> cerosEmparejados 2 3 [[1,1,1],[1,1,2],[1,2,1],[1,2,2],[1,0,0],[2,1,1],[2,1,2], [2,2,1],[2,2,2],[2,0,0],[0,0,1],[0,0,2]] ghci> cerosEmparejados 2 4 [[1,1,1,1],[1,1,1,2],[1,1,2,1],[1,1,2,2],[1,1,0,0],[1,2,1,1], [1,2,1,2],[1,2,2,1],[1,2,2,2],[1,2,0,0],[1,0,0,1],[1,0,0,2], [2,1,1,1],[2,1,1,2],[2,1,2,1],[2,1,2,2],[2,1,0,0],[2,2,1,1], [2,2,1,2],[2,2,2,1],[2,2,2,2],[2,2,0,0],[2,0,0,1],[2,0,0,2], [0,0,1,1],[0,0,1,2],[0,0,2,1],[0,0,2,2],[0,0,0,0]] |
- (nCerosEmparejados m n) es el número de listas de longitud n de ceros emparejados con los números 0, 1, 2,…, m. Por ejemplo,
|
1 2 3 4 |
nCerosEmparejados 2 2 == 5 nCerosEmparejados 2 3 == 12 nCerosEmparejados 2 4 == 29 nCerosEmparejados 9 27 == 79707842493701635611689499 |
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 |
import Data.List (genericIndex) import Data.List (genericLength) cerosEmparejados :: Integer -> Integer -> [[Integer]] cerosEmparejados m 0 = [[]] cerosEmparejados m 1 = [[k] | k <- [1..m]] cerosEmparejados m n = [x:ys | x <- [1..m], ys <- cerosEmparejados m (n-1)] ++ [0:0:ys | ys <- cerosEmparejados m (n-2)] -- 1ª definición de nCerosEmparejados: nCerosEmparejados1 :: Integer -> Integer -> Integer nCerosEmparejados1 m n = fromIntegral (length (cerosEmparejados m n)) -- 2ª definición de nCerosEmparejados: nCerosEmparejados2 :: Integer -> Integer -> Integer nCerosEmparejados2 _ 0 = 1 nCerosEmparejados2 m 1 = m nCerosEmparejados2 m n = m * nCerosEmparejados2 m (n-1) + nCerosEmparejados2 m (n-2) -- 3ª definición de nCerosEmparejados: nCerosEmparejados3 :: Integer -> Integer -> Integer nCerosEmparejados3 m n = aux `genericIndex` n where aux = 1 : m : zipWith (\x y -> x+m*y) aux (tail aux) -- Comparación de eficiencia -- ghci> nCerosEmparejados1 9 7 -- 5144589 -- (22.30 secs, 6556279384 bytes) -- ghci> nCerosEmparejados2 9 7 -- 5144589 -- (0.01 secs, 515464 bytes) -- ghci> nCerosEmparejados3 9 7 -- 5144589 -- (0.01 secs, 518104 bytes) -- -- ghci> nCerosEmparejados2 9 33 -- 45556060883025783396845717812863 -- (21.59 secs, 2676070480 bytes) -- ghci> nCerosEmparejados3 9 33 -- 45556060883025783396845717812863 -- (0.00 secs, 1017240 bytes) |