{"id":5870,"date":"2020-05-08T06:03:18","date_gmt":"2020-05-08T04:03:18","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5870"},"modified":"2020-05-15T18:59:44","modified_gmt":"2020-05-15T16:59:44","slug":"caminos-en-una-matriz","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/caminos-en-una-matriz\/","title":{"rendered":"Caminos en una matriz"},"content":{"rendered":"

Los caminos desde el extremo superior izquierdo (posici\u00f3n (1,1)) hasta el extremo inferior derecho (posici\u00f3n (3,4)) en la matriz<\/p>\n

\n   (  1  6 11  2 )\n   (  7 12  3  8 )\n   (  3  8  4  9 )\n<\/pre>\n
movi\u00e9ndose en cada paso una casilla hacia abajo o hacia la derecha, son los siguientes:<\/p>\n
\n   1, 7,  3, 8, 4, 9\n   1, 7, 12, 8, 4, 9\n   1, 7, 12, 3, 4, 9\n   1, 7, 12, 3, 8, 9\n   1, 6, 12, 8, 4, 9\n   1, 6, 12, 3, 4, 9\n   1, 6, 12, 3, 8, 9\n   1, 6, 11, 3, 4, 9\n   1, 6, 11, 3, 8, 9\n   1, 6, 11, 2, 8, 9\n<\/pre>\n
Definir la funci\u00f3n<\/p>\n
\n   caminos :: Matrix Int -> [[Int]]\n<\/pre>\n
tal que (caminos m) es la lista de los caminos en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, movi\u00e9ndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,<\/p>\n
\n   \u03bb> caminos (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])\n   [[1,7, 3,8,4,9],\n    [1,7,12,8,4,9],\n    [1,7,12,3,4,9],\n    [1,7,12,3,8,9],\n    [1,6,12,8,4,9],\n    [1,6,12,3,4,9],\n    [1,6,12,3,8,9],\n    [1,6,11,3,4,9],\n    [1,6,11,3,8,9],\n    [1,6,11,2,8,9]]\n   \u03bb> length (caminos (fromList 12 13 [1..]))\n   1352078\n<\/pre>\n
Nota<\/strong>: Se recomienda usar programaci\u00f3n din\u00e1mica.<\/p>\n
Soluciones<\/h4>\n
\nimport Data.Matrix\n\n-- 1\u00aa definici\u00f3n de caminos (por recursi\u00f3n)\n-- ----------------------------------------\n\ncaminos1 :: Matrix Int -> [[Int]]\ncaminos1 a = aux (1,1)\n  where\n    aux (i,j)\n      | i == m           = [[a!(i,k) | k <- [j..n]]]\n      | j == n           = [[a!(k,j) | k <- [i..m]]]\n      | otherwise        = [a!(i,j) : cs | cs <- aux (i+1,j) ++ aux (i,j+1)]\n      where m = nrows a\n            n = ncols a\n\n-- 2\u00aa soluci\u00f3n (mediante programaci\u00f3n din\u00e1mica)\n-- --------------------------------------------\n\ncaminos2 :: Matrix Int -> [[Int]]\ncaminos2 a = q ! (1,1)\n  where\n    q = matrix m n f\n    m = nrows a\n    n = ncols a\n    f (i,j) | i == m    = [[a!(i,k) | k <- [j..n]]]\n            | j == n    = [[a!(k,j) | k <- [i..m]]]\n            | otherwise = [a!(i,j) : cs | cs <- q!(i+1,j) ++ q!(i,j+1)]  \n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ncaminos3 :: Matrix Int -> [[Int]]\ncaminos3 a\n  | m == 1 || n == 1 = [toList a]\n  | otherwise = map (a ! (1,1):) (caminos3 (submatrix 2 m 1 n a) ++\n                                  caminos3 (submatrix 1 m 2 n a)) \n  where m = nrows a\n        n = ncols a\n\n-- Comparaci\u00f3n de eficiencia\n-- -------------------------\n\n--    \u03bb> length (caminos1 (fromList 11 11 [1..]))\n--    184756\n--    (4.15 secs, 738,764,712 bytes)\n--    \u03bb> length (caminos2 (fromList 11 11 [1..]))\n--    184756\n--    (0.74 secs, 115,904,952 bytes)\n--    \u03bb> length (caminos3 (fromList 11 11 [1..]))\n--    184756\n--    (2.22 secs, 614,472,136 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Los caminos desde el extremo superior izquierdo (posici\u00f3n (1,1)) hasta el extremo inferior derecho (posici\u00f3n (3,4)) en la matriz ( 1 6 11 2 ) ( 7 12 3 8 ) ( 3 8 4 9 ) movi\u00e9ndose en cada paso una casilla hacia abajo o hacia la derecha, son los siguientes: 1, 7, 3,…<\/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":[8,286,10,42,97,99,98,11,6,32],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5870"}],"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=5870"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5870\/revisions"}],"predecessor-version":[{"id":5898,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5870\/revisions\/5898"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5870"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5870"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5870"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}