Matrices de Toepliz
Una matriz de Toeplitz es una matriz cuadrada que es constante a lo largo de las diagonales paralelas a la diagonal principal. Por ejemplo,
|
1 2 3 4 |
|2 5 1 6| |2 5 1 6| |4 2 5 1| |4 2 6 1| |7 4 2 5| |7 4 2 5| |9 7 4 2| |9 7 4 2| |
la primera es una matriz de Toeplitz y la segunda no lo es.
Las anteriores matrices se pueden definir por
|
1 2 3 |
ej1, ej2 :: Array (Int,Int) Int ej1 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,5,1,7,4,2,5,9,7,4,2] ej2 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,6,1,7,4,2,5,9,7,4,2] |
Definir la función
|
1 |
esToeplitz :: Eq a => Array (Int,Int) a -> Bool |
tal que esToeplitz p se verifica si la matriz p es de Toeplitz. Por ejemplo,
|
1 2 |
esToeplitz ej1 == True esToeplitz ej2 == False |
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 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
import Data.Array (Array, (!), bounds, listArray) import Test.Hspec (Spec, describe, hspec, it, shouldBe) ej1, ej2 :: Array (Int,Int) Int ej1 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,5,1,7,4,2,5,9,7,4,2] ej2 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,6,1,7,4,2,5,9,7,4,2] -- 1ª solución -- =========== esToeplitz1 :: Eq a => Array (Int,Int) a -> Bool esToeplitz1 p = esCuadrada p && all todosIguales (diagonalesPrincipales p) -- (esCuadrada p) se verifica si la matriz p es cuadrada. Por ejemplo, -- esCuadrada (listArray ((1,1),(4,4)) [1..]) == True -- esCuadrada (listArray ((1,1),(3,4)) [1..]) == False esCuadrada :: Eq a => Array (Int,Int) a -> Bool esCuadrada p = m == n where (_,(m,n)) = bounds p -- (diagonalesPrincipales p) es la lista de las diagonales principales -- de p. Por ejemplo, -- λ> diagonalesPrincipales ej1 -- [[2,2,2,2],[5,5,5],[1,1],[6],[2,2,2,2],[4,4,4],[7,7],[9]] -- λ> diagonalesPrincipales ej2 -- [[2,2,2,2],[5,6,5],[1,1],[6],[2,2,2,2],[4,4,4],[7,7],[9]] diagonalesPrincipales :: Array (Int,Int) a -> [[a]] diagonalesPrincipales p = [[p ! i |i <- is] | is <- posicionesDiagonalesPrincipales m n] where (_,(m,n)) = bounds p -- (posicionesDiagonalesPrincipales m n) es la lista de las -- posiciones de las diagonales principales de una matriz con m filas y -- n columnas. Por ejemplo, -- λ> mapM_ print (posicionesDiagonalesPrincipales 3 4) -- [(3,1)] -- [(2,1),(3,2)] -- [(1,1),(2,2),(3,3)] -- [(1,2),(2,3),(3,4)] -- [(1,3),(2,4)] -- [(1,4)] -- λ> mapM_ print (posicionesDiagonalesPrincipales 4 4) -- [(4,1)] -- [(3,1),(4,2)] -- [(2,1),(3,2),(4,3)] -- [(1,1),(2,2),(3,3),(4,4)] -- [(1,2),(2,3),(3,4)] -- [(1,3),(2,4)] -- [(1,4)] -- λ> mapM_ print (posicionesDiagonalesPrincipales 4 3) -- [(4,1)] -- [(3,1),(4,2)] -- [(2,1),(3,2),(4,3)] -- [(1,1),(2,2),(3,3)] -- [(1,2),(2,3)] -- [(1,3)] posicionesDiagonalesPrincipales :: Int -> Int -> [[(Int, Int)]] posicionesDiagonalesPrincipales m n = [zip [i..m] [1..n] | i <- [m,m-1..1]] ++ [zip [1..m] [j..n] | j <- [2..n]] -- (todosIguales xs) se verifica si todos los elementos de xs son -- iguales. Por ejemplo, -- todosIguales [5,5,5] == True -- todosIguales [5,4,5] == False todosIguales :: Eq a => [a] -> Bool todosIguales [] = True todosIguales (x:xs) = all (== x) xs -- 2ª solución -- =========== esToeplitz2 :: Eq a => Array (Int,Int) a -> Bool esToeplitz2 p = m == n && and [p!(i,j) == p!(i+1,j+1) | i <- [1..n-1], j <- [1..n-1]] where (_,(m,n)) = bounds p -- Verificación -- ============ verifica :: IO () verifica = hspec spec specG :: (Array (Int,Int) Int -> Bool) -> Spec specG esToeplitz = do it "e1" $ esToeplitz ej1 `shouldBe` True it "e2" $ esToeplitz ej2 `shouldBe` False spec :: Spec spec = do describe "def. 1" $ specG esToeplitz1 describe "def. 2" $ specG esToeplitz2 -- La verificación es -- λ> verifica -- 4 examples, 0 failures -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> esToeplitz1 (listArray ((1,1),(2*10^3,2*10^3)) (repeat 1)) -- True -- (2.26 secs, 2,211,553,888 bytes) -- λ> esToeplitz2 (listArray ((1,1),(2*10^3,2*10^3)) (repeat 1)) -- True -- (4.26 secs, 3,421,651,032 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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
from timeit import Timer, default_timer from typing import TypeVar from src.Diagonales_principales import diagonalesPrincipales1 A = TypeVar('A') # 1ª solución # =========== ej1: list[list[int]] = [[2,5,1,6],[4,2,5,1],[7,4,2,5],[9,7,4,2]] ej2: list[list[int]] = [[2,5,1,6],[4,2,6,1],[7,4,2,5],[9,7,4,2]] # esCuadrada(p) se verifica si la matriz p es cuadrada. Por ejemplo, # >>> esCuadrada([[1,2],[3,4]]) == True # >>> esCuadrada([[1,2],[3,4],[5,6]]) == False # >>> esCuadrada([[1,2,3],[4,5,6]]) == False def esCuadrada(p : list[list[A]]) -> bool: return all(len(elemento) == len(p) for elemento in p) # todosIguales(xs) se verifica si todos los elementos de xs son # iguales. Por ejemplo, # todosIguales([5,5,5]) == True # todosIguales([5,4,5]) == False def todosIguales(xs: list[A]) -> bool: return all(x == xs[0] for x in xs) def esToeplitz1(p: list[list[A]]) -> bool: return esCuadrada(p) and all(todosIguales(xs) for xs in diagonalesPrincipales1(p)) # 2ª solución # =========== def esToeplitz2(p: list[list[A]]) -> bool: n = len(p) return all(len(xs) == n for xs in p) and \ all(p[i][j] == p[i+1][j+1] for i in range(0,n-1) for j in range(0,n-1)) # Verificación # ============ def test_esToeplitz() -> None: for esToeplitz in [esToeplitz1, esToeplitz2]: assert esToeplitz(ej1) assert not esToeplitz(ej2) print("Verificado") # La verificación es # >>> test_esToeplitz() # Verificado # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('esToeplitz1([[1]*2*10**3]*2*10**3)') # 1.52 segundos # >>> tiempo('esToeplitz2([[1]*2*10**3]*2*10**3)') # 0.51 segundos |