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]] |
1. Soluciones en Haskell
|
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 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
import Data.Array (Array, (!), bounds, listArray) import Test.Hspec (Spec, describe, hspec, it, shouldBe) 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]] -- Verificación -- ============ verifica :: IO () verifica = hspec spec specG :: (Array (Int,Int) Int -> [[Int]]) -> Spec specG diagonalesPrincipales = do it "e1" $ diagonalesPrincipales (listArray ((1,1),(3,4)) [1..12]) `shouldBe` [[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]] spec :: Spec spec = do describe "def. 1" $ specG diagonalesPrincipales1 describe "def. 2" $ specG diagonalesPrincipales2 -- La verificación es -- λ> verifica -- 2 examples, 0 failures -- Equivalencia de las definiciones -- ================================ -- La propiedad es prop_diagonalesPrincipales2 :: Positive Int -> Positive Int -> Bool prop_diagonalesPrincipales2 (Positive m) (Positive n) = diagonalesPrincipales1 p == diagonalesPrincipales2 p where p = listArray ((1,1),(m,n)) [1..] -- La comprobación es -- λ> quickCheck prop_diagonalesPrincipales2 -- +++ 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) |
2. Soluciones en Python
|
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 |
from typing import TypeVar from src.Posiciones_diagonales_principales import ( posicionesDiagonalesPrincipales1, posicionesDiagonalesPrincipales2) A = TypeVar('A') # 1ª solución # =========== matriz = list[list[A]] def diagonalesPrincipales1(p: matriz[A]) -> list[list[A]]: m = len(p) n = len(p[0]) return [[p[i-1][j-1] for (i,j) in ijs] for ijs in posicionesDiagonalesPrincipales1(m, n)] # 2ª solución # =========== def diagonalesPrincipales2(p: matriz[A]) -> list[list[A]]: m = len(p) n = len(p[0]) return [[p[i-1][j-1] for (i,j) in ijs] for ijs in posicionesDiagonalesPrincipales2(m, n)] # Verificación # ============ def test_diagonalesPrincipales() -> None: for diagonalesPrincipales in [diagonalesPrincipales1, diagonalesPrincipales2]: assert diagonalesPrincipales([[ 1, 2, 3, 4], [ 5, 6, 7, 8], [ 9,10,11,12]]) == \ [[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]] print("Verificado") # La verificación es # >>> test_diagonalesPrincipales() # Verificado |