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
Las matrices se pueden representar mediante tablas cuyos índices son pares de enteros
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]
Definir la función
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]
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)
Referencias
Basado en Matrix Fill-In del blog Programming Praxis.