{"id":1997,"date":"2016-01-19T06:00:36","date_gmt":"2016-01-19T04:00:36","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=1997"},"modified":"2016-01-26T07:44:55","modified_gmt":"2016-01-26T05:44:55","slug":"relleno-de-matrices","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/relleno-de-matrices\/","title":{"rendered":"Relleno de matrices"},"content":{"rendered":"<p>Dada una matriz cuyos elementos son 0 \u00f3 1, su <strong>relleno<\/strong> es la matriz obtenida haciendo iguales a 1 los elementos de las filas y de las columna que contienen alg\u00fan uno. Por ejemplo, el relleno de la matriz de la izquierda es la de la derecha:<\/p>\n<pre lang=\"text\"> \n   0 0 0 0 0    1 0 0 1 0\n   0 0 0 0 0    1 0 0 1 0\n   0 0 0 1 0    1 1 1 1 1\n   1 0 0 0 0    1 1 1 1 1\n   0 0 0 0 0    1 0 0 1 0\n<\/pre>\n<p>Las matrices se pueden representar mediante tablas cuyos \u00edndices son pares de enteros<\/p>\n<pre lang=\"text\"> \n   type Matriz = Array (Int,Int) Int\n<\/pre>\n<p>por ejemplo, la matriz de la izquierda de la figura anterior se define por<\/p>\n<pre lang=\"text\"> \n   ej :: Matriz                  \n   ej = listArray ((1,1),(5,5)) [0, 0, 0, 0, 0,\n                                 0, 0, 0, 0, 0,\n                                 0, 0, 0, 1, 0,\n                                 1, 0, 0, 0, 0,\n                                 0, 0, 0, 0, 0]\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\"> \n   relleno :: Matriz -> Matriz\n<\/pre>\n<p>tal que (relleno p) es el relleno de la matriz p. Por ejemplo,<\/p>\n<pre lang=\"text\"> \n   \u03bb> elems (relleno ej)\n   [1,0,0,1,0,\n    1,0,0,1,0,\n    1,1,1,1,1,\n    1,1,1,1,1,\n    1,0,0,1,0]\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Array\n\ntype Matriz = Array (Int,Int) Int\n\nej :: Matriz                  \nej = listArray ((1,1),(5,5)) [0, 0, 0, 0, 0,\n                              0, 0, 0, 0, 0,\n                              0, 0, 0, 1, 0,\n                              1, 0, 0, 0, 0,\n                              0, 0, 0, 0, 0]\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nrelleno1 :: Matriz -> Matriz\nrelleno1 p = \n    array ((1,1),(m,n)) [((i,j),f i j) | i <- [1..m], j <- [1..n]]\n    where (_,(m,n)) = bounds p\n          f i j | 1 `elem` [p!(i,k) | k <- [1..n]] = 1\n                | 1 `elem` [p!(k,j) | k <- [1..m]] = 1\n                | otherwise                        = 0\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nrelleno2 :: Matriz -> Matriz\nrelleno2 p = \n    array ((1,1),(m,n)) [((i,j),f i j) | i <- [1..m], j <- [1..n]]\n    where (_,(m,n)) = bounds p\n          filas     = filasConUno p\n          columnas  = columnasConUno p\n          f i j | i `elem` filas    = 1\n                | j `elem` columnas = 1\n                | otherwise         = 0\n\n-- (filasConUno p) es la lista de las filas de p que tienen alg\u00fan\n-- uno. Por ejemplo,\n--    filasConUno ej  ==  [3,4]\nfilasConUno :: Matriz -> [Int]\nfilasConUno p = [i | i <- [1..m], filaConUno p i]\n    where (_,(m,n)) = bounds p\n\n-- (filaConUno p i) se verifica si p tiene alg\u00fan uno en la fila i. Por\n-- ejemplo, \n--    filaConUno ej 3  ==  True\n--    filaConUno ej 2  ==  False\nfilaConUno :: Matriz -> Int -> Bool\nfilaConUno p i = any (==1) [p!(i,j) | j <- [1..n]]\n    where (_,(_,n)) = bounds p\n\n-- (columnasConUno p) es la lista de las columnas de p que tienen alg\u00fan\n-- uno. Por ejemplo,\n--    columnasConUno ej  ==  [1,4]\ncolumnasConUno :: Matriz -> [Int]\ncolumnasConUno p = [j | j <- [1..n], columnaConUno p j]\n    where (_,(m,n)) = bounds p\n\n-- (columnaConUno p i) se verifica si p tiene alg\u00fan uno en la columna i. Por\n-- ejemplo, \n--    columnaConUno ej 1  ==  True\n--    columnaConUno ej 2  ==  False\ncolumnaConUno :: Matriz -> Int -> Bool\ncolumnaConUno p j = any (==1) [p!(i,j) | i <- [1..m]]\n    where (_,(m,_)) = bounds p\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nrelleno3 :: Matriz -> Matriz\nrelleno3 p = p \/\/ ([((i,j),1) | i <- filas,  j <- [1..n]] ++ \n                   [((i,j),1) | i <- [1..m], j <- columnas])\n  where (_,(m,n)) = bounds p\n        filas     = filasConUno p\n        columnas  = columnasConUno p\n\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> let f i j = if i == j then 1 else 0 \n--    \u03bb> let q n = array ((1,1),(n,n)) [((i,j),f i j) | i <- [1..n], j <- [1..n]]\n--    \n--    \u03bb> sum (elems (relleno1 (q 200)))\n--    40000\n--    (6.90 secs, 1,877,369,544 bytes)\n--    \n--    \u03bb> sum (elems (relleno2 (q 200)))\n--    40000\n--    (0.46 secs, 57,354,168 bytes)\n--    \n--    \u03bb> sum (elems (relleno3 (q 200)))\n--    40000\n--    (0.34 secs, 80,465,144 bytes)\n--    \n--    \u03bb> sum (elems (relleno2 (q 500)))\n--    250000\n--    (4.33 secs, 353,117,640 bytes)\n--    \n--    \u03bb> sum (elems (relleno3 (q 500)))\n--    250000\n--    (2.40 secs, 489,630,048 bytes)\n<\/pre>\n<h4>Referencias<\/h4>\n<p>Basado en <a href=\"http:\/\/bit.ly\/207DMtX\">Matrix Fill-In<\/a> del blog <a href=\"http:\/\/programmingpraxis.com\">Programming Praxis<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Dada una matriz cuyos elementos son 0 \u00f3 1, su relleno es la matriz obtenida haciendo iguales a 1 los elementos de las filas y de las columna que contienen alg\u00fan uno. Por ejemplo, el relleno de la matriz de la izquierda es la de la derecha: 0 0 0 0 0 1 0 0&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[4],"tags":[250,43,26,245,72],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1997"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=1997"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1997\/revisions"}],"predecessor-version":[{"id":2045,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1997\/revisions\/2045"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=1997"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=1997"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=1997"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}