Diagonales principales de una matriz
La lista de las diagonales principales de la matriz
|
1 2 3 |
1 2 3 4 5 6 7 8 9 10 11 12 |
es
|
1 |
[[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]] |
Definir la función
|
1 |
diagonalesPrincipales :: Array (Int,Int) a -> [[a]] |
tal que (diagonalesPrincipales p) es la lista de las diagonales principales de p. Por ejemplo,
|
1 2 |
λ> diagonalesPrincipales (listArray ((1,1),(3,4)) [1..12]) [[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]] |
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 48 49 50 51 52 53 |
import Data.Array (Array, (!), bounds, listArray) import Test.QuickCheck -- 1ª solución -- =========== diagonalesPrincipales1 :: Array (Int,Int) a -> [[a]] diagonalesPrincipales1 p = [[p ! ij | ij <- ijs] | ijs <- posicionesDiagonalesPrincipales1 m n] where (_,(m,n)) = bounds p posicionesDiagonalesPrincipales1 :: Int -> Int -> [[(Int, Int)]] posicionesDiagonalesPrincipales1 m n = [extension ij | ij <- iniciales] where iniciales = [(i,1) | i <- [m,m-1..2]] ++ [(1,j) | j <- [1..n]] extension (i,j) = [(i+k,j+k) | k <- [0..min (m-i) (n-j)]] -- 2ª solución -- =========== diagonalesPrincipales2 :: Array (Int,Int) a -> [[a]] diagonalesPrincipales2 p = [[p ! ij | ij <- ijs] | ijs <- posicionesDiagonalesPrincipales2 m n] where (_,(m,n)) = bounds p posicionesDiagonalesPrincipales2 :: Int -> Int -> [[(Int, Int)]] posicionesDiagonalesPrincipales2 m n = [zip [i..m] [1..n] | i <- [m,m-1..1]] ++ [zip [1..m] [j..n] | j <- [2..n]] -- Equivalencia de las definiciones -- ================================ -- La propiedad es prop_diagonalesPrincipales :: Positive Int -> Positive Int -> Bool prop_diagonalesPrincipales (Positive m) (Positive n) = diagonalesPrincipales1 p == diagonalesPrincipales2 p where p = listArray ((1,1),(m,n)) [1..] -- La comprobación es -- λ> quickCheck prop_diagonalesPrincipales -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (diagonalesPrincipales1 (listArray ((1,1),(10^4,10^4)) [1..])) -- 19999 -- (6.90 secs, 8,010,369,224 bytes) -- λ> length (diagonalesPrincipales2 (listArray ((1,1),(10^4,10^4)) [1..])) -- 19999 -- (6.78 secs, 8,008,289,224 bytes) |
El código se encuentra en GitHub