Menu Close

Diagonales de matrices como listas

José A. Alonso,

Las matrices se pueden representar como listas de listas de la misma longitud, donde cada uno de sus elementos representa una fila de la matriz.

Definir la función

   diagonal :: [[a]] -> [a]

tal que (diagonal xss) es la diagonal de la matriz xss. Por ejemplo,

   diagonal [[3,5,2],[4,7,1],[6,9,0]]           ==  [3,7,0]
   diagonal [[3,5],[4,7],[6,9]]                 ==  [3,7]
   diagonal [[3,5,2],[4,7,1]]                   ==  [3,7]
   sum (diagonal (replicate 20000 [1..20000]))  ==  200010000

Soluciones

import Data.Array  ((!), listArray)
import Data.Matrix (fromLists, getDiag)
import Data.Vector (toList)
 
-- 1ª definición (por recursión):
diagonal1 :: [[a]] -> [a]
diagonal1 ((x:_):xss) = x : diagonal1 [tail xs | xs <- xss]
diagonal1 _           = []
 
-- 2ª definición (por comprensión):
diagonal2 :: [[a]] -> [a]
diagonal2 xss = [xs!!k | (xs,k) <- zip xss [0..n]]
    where n = length (head xss) - 1
 
-- 3ª definición (con Data.Matrix)
diagonal3 :: [[a]] -> [a]
diagonal3 = toList . getDiag . fromLists
 
-- 4ª definición (con Data.Array)
diagonal4 :: [[a]] -> [a]
diagonal4 xss = [p!(i,i) | i <- [1..k]] 
    where m = length xss
          n = length (head xss)
          k = min m n
          p = listArray ((1,1),(m,n)) (concat xss)
 
-- Comparación de eficiencia
--    λ> let n = 3000 in sum (diagonal1 (replicate n [1..n]))
--    4501500
--    (2.08 secs, 754,089,992 bytes)
--    λ> let n = 3000 in sum (diagonal2 (replicate n [1..n]))
--    4501500
--    (0.06 secs, 0 bytes)
--    λ> let n = 3000 in sum (diagonal3 (replicate n [1..n]))
--    4501500
--    (1.22 secs, 1,040,787,360 bytes)
--    λ> let n = 3000 in sum (diagonal4 (replicate n [1..n]))
--    4501500
--    (0.96 secs, 624,463,632 bytes)

Solución con Maxima

diagonal (xss) := block ([A],
  A : apply (matrix, xss),
  [m,n] : matrix_size (A),
  k : min (m,n),
  makelist (A[i,i],i,k))$
Posted in Ejercicio
Tagged , , , , , , , , , , ,

8 Comments

  1. carruirui3
    Responder 
    import Data.List (transpose)
 
diagonal :: [[a]] -> [a]
diagonal xss@(xs:_) | length xs < length xss = diagonal $ transpose xss
                    | otherwise = aux 0 xss
  where aux n [] = []
        aux n (xs:xss) = xs!!n : aux (n+1) xss
  2. carruirui3
    Responder 
    diagonal xss@(xs:_) = map ((i,fila) -> fila!!i) $ zip [0..] $ take (length xs) xss
  3. carruirui3
    Responder

    Utilizando las librerías, aunque es mucho más lento:

    import qualified Data.Matrix as M
import qualified Data.Vector as V
 
diagonal = V.toList . M.getDiag . M.fromLists
  4. alvalvdom1
    Responder 
    diagonal :: [[a]] -> [a]
diagonal [] = []
diagonal xss@(xs:_) = [(xss!!i)!!i | i <- [0..(min (length xss) (length xs))-1]]
  5. javoliher
    Responder 
     
diagonal :: [[a]] -> [a]
diagonal xss = aux 0 xss
 
aux n []       = []
aux n (xs:xss) |n < length xs = xs !! n : aux (n+1) xss
               |otherwise = []
  6. fracruzam
    Responder 
    diagonal :: [[a]] -> [a]
diagonal []       = []
diagonal ys@(x:_) = zipWith (i v -> v !! i) [0..length x - 1] ys
  7. abrdelrod
    Responder 
    diagonal :: [[a]] -> [a]
diagonal (xs:xss) 
    | any (/= length xs) (map length xss) = 
        error "Todas las listas no tienen la misma longitud"
    | otherwise = aux 0 (xs:xss)
    where aux n (ys:yss) | n < length xs = head (drop n ys) : aux (n+1) yss
                         | otherwise     = []
          aux _ _ = []
  8. antmacrui
    Responder

    Con Maxima

    diagonal (xss) := block ([A],
  A : apply (matrix, xss),
  [m,n] : matrix_size (A),
  k : min (m,n),
  makelist (A[i,i],i,k))$

Leave a Reply to abrdelrodCancel reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.