Matrices de Pascal
El triángulo de Pascal es un triángulo de números
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 ...............
construido de la siguiente forma
- la primera fila está formada por el número 1;
- las filas siguientes se construyen sumando los números adyacentes de la fila superior y añadiendo un 1 al principio y al final de la fila.
La matriz de Pascal es la matriz cuyas filas son los elementos de la correspondiente fila del triángulo de Pascal completadas con ceros. Por ejemplo, la matriz de Pascal de orden 6 es
|1 0 0 0 0 0| |1 1 0 0 0 0| |1 2 1 0 0 0| |1 3 3 1 0 0| |1 4 6 4 1 0| |1 5 10 10 5 1|
Definir la función
matrizPascal :: Int -> Matrix Integer
tal que (matrizPascal n) es la matriz de Pascal de orden n. Por ejemplo,
λ> matrizPascal 6 ( 1 0 0 0 0 0 ) ( 1 1 0 0 0 0 ) ( 1 2 1 0 0 0 ) ( 1 3 3 1 0 0 ) ( 1 4 6 4 1 0 ) ( 1 5 10 10 5 1 )
Soluciones
import Data.Matrix -- 1ª solución -- =========== matrizPascal :: Int -> Matrix Integer matrizPascal 1 = fromList 1 1 [1] matrizPascal n = matrix n n f where f (i,j) | i < n && j < n = p!(i,j) | i < n && j == n = 0 | j == 1 || j == n = 1 | otherwise = p!(i-1,j-1) + p!(i-1,j) p = matrizPascal (n-1) -- 2ª solución -- =========== matrizPascal2 :: Int -> Matrix Integer matrizPascal2 n = fromLists xss where yss = take n pascal xss = map (take n) (map (++ repeat 0) yss) pascal :: [[Integer]] pascal = [1] : map f pascal where f xs = zipWith (+) (0:xs) (xs ++ [0]) -- 3ª solución -- =========== matrizPascal3 :: Int -> Matrix Integer matrizPascal3 n = matrix n n f where f (i,j) | i >= j = comb (i-1) (j-1) | otherwise = 0 -- (comb n k) es el número de combinaciones (o coeficiente binomial) de -- n sobre k. Por ejemplo, comb :: Int -> Int -> Integer comb n k = product [n',n'-1..n'-k'+1] `div` product [1..k'] where n' = fromIntegral n k' = fromIntegral k -- Comparación de eficiencia -- ========================= -- λ> maximum (matrizPascal 150) -- 46413034868354394849492907436302560970058760 -- (2.58 secs, 394,030,504 bytes) -- λ> maximum (matrizPascal2 150) -- 46413034868354394849492907436302560970058760 -- (0.03 secs, 8,326,784 bytes) -- λ> maximum (matrizPascal3 150) -- 46413034868354394849492907436302560970058760 -- (0.38 secs, 250,072,360 bytes)