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]

1	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

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)

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

diagonal (xss) := block ([A],

A : apply (matrix, xss),

[m,n] : matrix_size (A),

k : min (m,n),

makelist (A[i,i],i,k))$

8 Comentarios

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

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

Responder

diagonal xss@(xs:_) = map (\(i,fila) -> fila!!i) $ zip [0..] $ take (length xs) xss

1	diagonal xss@(xs:_) = map (\(i,fila) -> fila!!i) $ zip [0..] $ take (length xs) xss

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

import qualified Data.Matrix as M

import qualified Data.Vector as V

diagonal = V.toList . M.getDiag . M.fromLists

Responder

diagonal :: [[a]] -> [a]
diagonal [] = []
diagonal xss@(xs:_) = [(xss!!i)!!i | i <- [0..(min (length xss) (length xs))-1]]

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

diagonal [] = []

diagonal xss@(xs:_) = [(xss!!i)!!i | i <- [0..(min (length xss) (length xs))-1]]

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 = []

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

diagonal xss = aux 0 xss

aux n [] = []

aux n (xs:xss) |n < length xs = xs !! n : aux (n+1) xss

|otherwise = []

Responder

diagonal :: [[a]] -> [a]
diagonal []       = []
diagonal ys@(x:_) = zipWith (\i v -> v !! i) [0..length x - 1] ys

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

diagonal [] = []

diagonal ys@(x:_) = zipWith (\i v -> v !! i) [0..length x - 1] ys

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 _ _ = []

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 _ _ = []

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

diagonal (xss) := block ([A],

A : apply (matrix, xss),

[m,n] : matrix_size (A),

k : min (m,n),

makelist (A[i,i],i,k))$

Responder

Diagonales de matrices como listas

Soluciones

Solución con Maxima

8 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Solución con Maxima

Se puede imprimir o compartir con

8 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico