Relleno de matrices

Dada una matriz cuyos elementos son 0 ó 1, su relleno es la matriz obtenida haciendo iguales a 1 los elementos de las filas y de las columna que contienen algún uno. Por ejemplo, el relleno de la matriz de la izquierda es la de la derecha:

   0 0 0 0 0    1 0 0 1 0
   0 0 0 0 0    1 0 0 1 0
   0 0 0 1 0    1 1 1 1 1
   1 0 0 0 0    1 1 1 1 1
   0 0 0 0 0    1 0 0 1 0

0 0 0 0 0 1 0 0 1 0

0 0 0 1 0 1 1 1 1 1

1 0 0 0 0 1 1 1 1 1

0 0 0 0 0 1 0 0 1 0

Las matrices se pueden representar mediante tablas cuyos índices son pares de enteros

   type Matriz = Array (Int,Int) Int

1	type Matriz = Array (Int,Int) Int

por ejemplo, la matriz de la izquierda de la figura anterior se define por

   ej :: Matriz                  
   ej = listArray ((1,1),(5,5)) [0, 0, 0, 0, 0,
                                 0, 0, 0, 0, 0,
                                 0, 0, 0, 1, 0,
                                 1, 0, 0, 0, 0,
                                 0, 0, 0, 0, 0]

ej :: Matriz

ej = listArray ((1,1),(5,5)) [0, 0, 0, 0, 0,

0, 0, 0, 0, 0,

0, 0, 0, 1, 0,

1, 0, 0, 0, 0,

0, 0, 0, 0, 0]

Definir la función

   relleno :: Matriz -> Matriz

1	relleno :: Matriz -> Matriz

tal que (relleno p) es el relleno de la matriz p. Por ejemplo,

   λ> elems (relleno ej)
   [1,0,0,1,0,
    1,0,0,1,0,
    1,1,1,1,1,
    1,1,1,1,1,
    1,0,0,1,0]

λ> elems (relleno ej)

[1,0,0,1,0,

1,0,0,1,0,

1,1,1,1,1,

1,0,0,1,0]

Soluciones

import Data.Array

type Matriz = Array (Int,Int) Int

ej :: Matriz                  
ej = listArray ((1,1),(5,5)) [0, 0, 0, 0, 0,
                              0, 0, 0, 0, 0,
                              0, 0, 0, 1, 0,
                              1, 0, 0, 0, 0,
                              0, 0, 0, 0, 0]

-- 1ª solución
-- ===========

relleno1 :: Matriz -> Matriz
relleno1 p = 
    array ((1,1),(m,n)) [((i,j),f i j) | i <- [1..m], j <- [1..n]]
    where (_,(m,n)) = bounds p
          f i j | 1 `elem` [p!(i,k) | k <- [1..n]] = 1
                | 1 `elem` [p!(k,j) | k <- [1..m]] = 1
                | otherwise                        = 0

-- 2ª solución
-- ===========

relleno2 :: Matriz -> Matriz
relleno2 p = 
    array ((1,1),(m,n)) [((i,j),f i j) | i <- [1..m], j <- [1..n]]
    where (_,(m,n)) = bounds p
          filas     = filasConUno p
          columnas  = columnasConUno p
          f i j | i `elem` filas    = 1
                | j `elem` columnas = 1
                | otherwise         = 0

-- (filasConUno p) es la lista de las filas de p que tienen algún
-- uno. Por ejemplo,
--    filasConUno ej  ==  [3,4]
filasConUno :: Matriz -> [Int]
filasConUno p = [i | i <- [1..m], filaConUno p i]
    where (_,(m,n)) = bounds p

-- (filaConUno p i) se verifica si p tiene algún uno en la fila i. Por
-- ejemplo, 
--    filaConUno ej 3  ==  True
--    filaConUno ej 2  ==  False
filaConUno :: Matriz -> Int -> Bool
filaConUno p i = any (==1) [p!(i,j) | j <- [1..n]]
    where (_,(_,n)) = bounds p

-- (columnasConUno p) es la lista de las columnas de p que tienen algún
-- uno. Por ejemplo,
--    columnasConUno ej  ==  [1,4]
columnasConUno :: Matriz -> [Int]
columnasConUno p = [j | j <- [1..n], columnaConUno p j]
    where (_,(m,n)) = bounds p

-- (columnaConUno p i) se verifica si p tiene algún uno en la columna i. Por
-- ejemplo, 
--    columnaConUno ej 1  ==  True
--    columnaConUno ej 2  ==  False
columnaConUno :: Matriz -> Int -> Bool
columnaConUno p j = any (==1) [p!(i,j) | i <- [1..m]]
    where (_,(m,_)) = bounds p

-- 3ª solución
-- ===========

relleno3 :: Matriz -> Matriz
relleno3 p = p // ([((i,j),1) | i <- filas,  j <- [1..n]] ++ 
                   [((i,j),1) | i <- [1..m], j <- columnas])
  where (_,(m,n)) = bounds p
        filas     = filasConUno p
        columnas  = columnasConUno p


-- Comparación de eficiencia
-- =========================

--    λ> let f i j = if i == j then 1 else 0 
--    λ> let q n = array ((1,1),(n,n)) [((i,j),f i j) | i <- [1..n], j <- [1..n]]
--    
--    λ> sum (elems (relleno1 (q 200)))
--    40000
--    (6.90 secs, 1,877,369,544 bytes)
--    
--    λ> sum (elems (relleno2 (q 200)))
--    40000
--    (0.46 secs, 57,354,168 bytes)
--    
--    λ> sum (elems (relleno3 (q 200)))
--    40000
--    (0.34 secs, 80,465,144 bytes)
--    
--    λ> sum (elems (relleno2 (q 500)))
--    250000
--    (4.33 secs, 353,117,640 bytes)
--    
--    λ> sum (elems (relleno3 (q 500)))
--    250000
--    (2.40 secs, 489,630,048 bytes)

100

101

import Data.Array

type Matriz = Array (Int,Int) Int

ej :: Matriz

ej = listArray ((1,1),(5,5)) [0, 0, 0, 0, 0,

0, 0, 0, 0, 0,

0, 0, 0, 1, 0,

1, 0, 0, 0, 0,

0, 0, 0, 0, 0]

-- 1ª solución

-- ===========

relleno1 :: Matriz -> Matriz

relleno1 p =

array ((1,1),(m,n)) [((i,j),f i j) | i <- [1..m], j <- [1..n]]

where (_,(m,n)) = bounds p

f i j | 1 `elem` [p!(i,k) | k <- [1..n]] = 1

| 1 `elem` [p!(k,j) | k <- [1..m]] = 1

| otherwise = 0

-- 2ª solución

-- ===========

relleno2 :: Matriz -> Matriz

relleno2 p =

array ((1,1),(m,n)) [((i,j),f i j) | i <- [1..m], j <- [1..n]]

where (_,(m,n)) = bounds p

filas = filasConUno p

columnas = columnasConUno p

f i j | i `elem` filas = 1

| j `elem` columnas = 1

| otherwise = 0

-- (filasConUno p) es la lista de las filas de p que tienen algún

-- uno. Por ejemplo,

-- filasConUno ej == [3,4]

filasConUno :: Matriz -> [Int]

filasConUno p = [i | i <- [1..m], filaConUno p i]

where (_,(m,n)) = bounds p

-- (filaConUno p i) se verifica si p tiene algún uno en la fila i. Por

-- ejemplo,

-- filaConUno ej 3 == True

-- filaConUno ej 2 == False

filaConUno :: Matriz -> Int -> Bool

filaConUno p i = any (==1) [p!(i,j) | j <- [1..n]]

where (_,(_,n)) = bounds p

-- (columnasConUno p) es la lista de las columnas de p que tienen algún

-- uno. Por ejemplo,

-- columnasConUno ej == [1,4]

columnasConUno :: Matriz -> [Int]

columnasConUno p = [j | j <- [1..n], columnaConUno p j]

where (_,(m,n)) = bounds p

-- (columnaConUno p i) se verifica si p tiene algún uno en la columna i. Por

-- ejemplo,

-- columnaConUno ej 1 == True

-- columnaConUno ej 2 == False

columnaConUno :: Matriz -> Int -> Bool

columnaConUno p j = any (==1) [p!(i,j) | i <- [1..m]]

where (_,(m,_)) = bounds p

-- 3ª solución

-- ===========

relleno3 :: Matriz -> Matriz

relleno3 p = p // ([((i,j),1) | i <- filas, j <- [1..n]] ++

[((i,j),1) | i <- [1..m], j <- columnas])

where (_,(m,n)) = bounds p

filas = filasConUno p

columnas = columnasConUno p

-- Comparación de eficiencia

-- =========================

-- λ> let f i j = if i == j then 1 else 0

-- λ> let q n = array ((1,1),(n,n)) [((i,j),f i j) | i <- [1..n], j <- [1..n]]

-- λ> sum (elems (relleno1 (q 200)))

-- 40000

-- (6.90 secs, 1,877,369,544 bytes)

-- λ> sum (elems (relleno2 (q 200)))

-- 40000

-- (0.46 secs, 57,354,168 bytes)

-- λ> sum (elems (relleno3 (q 200)))

-- 40000

-- (0.34 secs, 80,465,144 bytes)

-- λ> sum (elems (relleno2 (q 500)))

-- 250000

-- (4.33 secs, 353,117,640 bytes)

-- λ> sum (elems (relleno3 (q 500)))

-- 250000

-- (2.40 secs, 489,630,048 bytes)

Referencias

Basado en Matrix Fill-In del blog Programming Praxis.

4 Comentarios

import Data.Array
import Data.Ratio

relleno :: Matriz -> Matriz
relleno p = array ((1,1),(x,y)) [((i,j), f i j) | i <- [1..x], j <- [1..y]]
    where primCoord p = [fst x | (x,y) <- assocs p, y == 1]
          segCoord p  = [snd x | (x,y) <- assocs p, y == 1]
          x = fst . snd $ bounds p
          y = snd . snd $ bounds p
          f i j | elem i (primCoord p) = 1
                | elem j (segCoord p)  = 1
                | otherwise            = 0

import Data.Ratio

relleno p = array ((1,1),(x,y)) [((i,j), f i j) | i <- [1..x], j <- [1..y]]

where primCoord p = [fst x | (x,y) <- assocs p, y == 1]

segCoord p = [snd x | (x,y) <- assocs p, y == 1]

x = fst . snd $ bounds p

y = snd . snd $ bounds p

f i j | elem i (primCoord p) = 1

| elem j (segCoord p) = 1

Responder

relleno :: Matriz -> Matriz
relleno p = p // ([((n,x),1) | n <- filas,    x <- [1..f]] ++ 
                  [((y,m),1) | m <- columnas, y <- [1..c]])
  where (f,c)    = snd $ bounds p
        filas    = [x | ((x,_),1) <- assocs p]
        columnas = [x | ((_,x),1) <- assocs p]

relleno p = p // ([((n,x),1) | n <- filas, x <- [1..f]] ++

[((y,m),1) | m <- columnas, y <- [1..c]])

where (f,c) = snd $ bounds p

filas = [x | ((x,_),1) <- assocs p]

columnas = [x | ((_,x),1) <- assocs p]

relleno :: Matriz → Matriz
relleno m =
  let (a,f,h,v) = (A.assocs m, λs → M.fromListWith max (first s ↥ a), f fst, f snd)
  in  A.listArray (A.bounds m) [max (h!x) (v!y) | (x, y) ← fst ↥ a]

relleno :: Matriz → Matriz

relleno m =

let (a,f,h,v) = (A.assocs m, λs → M.fromListWith max (first s ↥ a), f fst, f snd)

in A.listArray (A.bounds m) [max (h!x) (v!y) | (x, y) ← fst ↥ a]

relleno :: Matriz -> Matriz
relleno t = array p [fx ((i,j),x) s | ((i,j),x) <- assocs t]
                where p = bounds t 
                      s = lista t 

lista t = [(i,j) | ((i,j),1) <- assocs t]

fx ((i,j),x) [] = ((i,j),x)
fx ((i,j), x) ((a,b):xs) | i == a || j == b = ((i,j),1)
                         | otherwise = fx ((i,j),x) xs

relleno t = array p [fx ((i,j),x) s | ((i,j),x) <- assocs t]

where p = bounds t

s = lista t

lista t = [(i,j) | ((i,j),1) <- assocs t]

fx ((i,j),x) [] = ((i,j),x)

fx ((i,j), x) ((a,b):xs) | i == a || j == b = ((i,j),1)

| otherwise = fx ((i,j),x) xs

Relleno de matrices

Soluciones

Referencias

4 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Referencias

Se puede imprimir o compartir con

4 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico