Menu Close

Diagonales de matrices como listas

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))$

8 soluciones de “Diagonales de matrices como listas

  1. carruirui3
    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
    diagonal xss@(xs:_) = map ((i,fila) -> fila!!i) $ zip [0..] $ take (length xs) xss
  3. carruirui3

    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
    diagonal :: [[a]] -> [a]
    diagonal [] = []
    diagonal xss@(xs:_) = [(xss!!i)!!i | i <- [0..(min (length xss) (length xs))-1]]
  5. javoliher
     
    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
    diagonal :: [[a]] -> [a]
    diagonal []       = []
    diagonal ys@(x:_) = zipWith (i v -> v !! i) [0..length x - 1] ys
  7. abrdelrod
    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

    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 alvalvdom1 Cancel reply

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