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,
|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
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
esToeplitz :: Eq a => Array (Int,Int) a -> Bool
tal que (esToeplitz p) se verifica si la matriz p es de Toeplitz. Por ejemplo,
esToeplitz ej1 == True esToeplitz ej2 == False
Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.
Soluciones
A continuación se muestran
- las soluciones en Haskell,
- las soluciones en Python y
- las soluciones en Common Lisp
1. Soluciones en Haskell
module Matriz_Toeplitz where 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
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) # posicionesdiagonalesprincipales(m, n) es la lista de las posiciones de # las diagonales principales de una matriz con m filas y n columnas. Por # ejemplo, # >>> posicionesDiagonalesPrincipales1(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)]] def posicionesDiagonalesPrincipales1(m: int, n: int) -> matriz: def iniciales() -> list[tuple[int, int]]: return [(i,1) for i in range(m,1,-1)] + [(1,j) for j in range(1, n+1)] def extension(p: tuple[int, int]) -> list[tuple[int, int]]: (i,j) = p return [(i+k,j+k) for k in range(0, 1+min(m-i, n-j))] return [extension(ij) for ij in iniciales()] # diagonalesPrincipales(p) es la lista de las diagonales principales de # p. Por ejemplo, # >>> diagonalesPrincipales1([[1,2,3,4],[5,6,7,8],[9,10,11,12]]) # [[9], [5, 10], [1, 6, 11], [2, 7, 12], [3, 8], [4]] 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)] 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
3. Soluciones en Common Lisp
(ql:quickload "fiveam" :silent t) (defpackage :matriz-toeplitz (:use :cl :fiveam)) (in-package :matriz-toeplitz) (defvar ej1 (make-array '(4 4) :initial-contents '((2 5 1 6) (4 2 5 1) (7 4 2 5) (9 7 4 2)))) (defvar ej2 (make-array '(4 4) :initial-contents '((2 5 1 6) (4 2 6 1) (7 4 2 5) (9 7 4 2)))) ;;; 1ª solución ;;; =========== ;;; (esCuadrada p) se verifica si la matriz p es cuadrada. Por ejemplo, ;;; > (es-cuadrada (make-array '(4 4))) ;;; T ;;; > (es-cuadrada (make-array '(4 3))) ;;; NIL (defun es-cuadrada (p) (= (array-dimension p 0) (array-dimension p 1))) ;;; (posicionesDiagonalesPrincipales m n) es la lista de las ;;; posiciones de las diagonales principales de una matriz con m filas y ;;; n columnas. Por ejemplo, ;;; > (posiciones-diagonales-principales 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))) (defun posiciones-diagonales-principales (m n) (append (loop for i from m downto 1 collect (loop for r from i to m for c from 1 to n collect (list r c))) (loop for j from 2 to n collect (loop for r from 1 to m for c from j to n collect (list r c))))) ;;; (diagonalesPrincipales p) es la lista de las diagonales principales ;;; de p. Por ejemplo, ;;; > (diagonales-principales (make-array '(3 4) ;;; :initial-contents '((1 2 3 4) ;;; (5 6 7 8) ;;; (9 10 11 12)))) ;;; ((9) (5 10) (1 6 11) (2 7 12) (3 8) (4)) (defun diagonales-principales (p) (let ((m (array-dimension p 0)) (n (array-dimension p 1))) (mapcar (lambda (ijs) (mapcar (lambda (ij) (aref p (1- (first ij)) (1- (second ij)))) ijs)) (posiciones-diagonales-principales m n)))) ;;; (todosIguales xs) se verifica si todos los elementos de xs son ;;; iguales. Por ejemplo, ;;; > (todos-iguales '(5 5 5)) ;;; T ;;; > (todos-iguales '(5 4 5)) ;;; NIL (defun todos-iguales (xs) (every (lambda (x) (eql x (first xs))) xs)) (defun es-toeplitz1 (p) (and (es-cuadrada p) (every #'todos-iguales (diagonales-principales p)))) ;;; 2ª solución ;;; =========== (defun es-toeplitz2 (p) (let ((m (array-dimension p 0)) (n (array-dimension p 1))) (and (= m n) (loop for i from 0 to (- m 2) always (loop for j from 0 to (- n 2) always (= (aref p i j) (aref p (+ i 1) (+ j 1)))))))) ;;; Verificación ;;; ============ (test es-toeplitz (mapc (lambda (es-toeplitz) (is-true (funcall es-toeplitz ej1)) (is-false (funcall es-toeplitz ej2))) '(es-toeplitz1 es-toeplitz2))) (defun verifica () (run 'es-toeplitz)) ;;; La verificación es ;;; (verifica) ;;; ;;; Running test ES-TOEPLITZ .... ;;; Comparación de eficiencia ;;; ========================= ;;; La comparación es ;;; > (time (es-toeplitz1 (make-array '(3000 3000)))) ;;; 1.282 seconds of real time ;;; > (time (es-toeplitz2 (make-array '(3000 3000)))) ;;; 0.362 seconds of real time