{"id":577,"date":"2014-11-17T07:56:35","date_gmt":"2014-11-17T05:56:35","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=577"},"modified":"2014-12-27T21:50:21","modified_gmt":"2014-12-27T19:50:21","slug":"mayores-elementos-de-una-matriz","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/mayores-elementos-de-una-matriz\/","title":{"rendered":"Mayores elementos de una matriz"},"content":{"rendered":"<h4>Enunciado<\/h4>\n<pre lang=\"text\">\n-- Las matrices se pueden representar mediante listas de listas. Por\n-- ejemplo, la matriz\n--    |3 2 5|\n--    |4 9 7|\n-- se puede representar por [[3,2,5],[4,9,7]].\n-- \n-- Definir la funci\u00f3n\n--    mayores :: Ord a => Int -> [[a]] -> [(a,Int)]\n-- tal que (mayores n xss) es la lista de los n mayores elementos de la\n-- matriz xss junto con sus correspondientes n\u00famero de fila. Por\n-- ejemplo,\n--    ghci> mayores 4 [[4,26,9],[2,37,53],[41,1,8]]\n--    [(53,2),(41,3),(37,2),(26,1)]\n-- \n-- Comprobar con QuickCheck que todos los elementos de (mayores n xss)\n-- son mayores o iguales que los restantes elementos de xss.\n-- \n-- Nota: Se pueden usar las funciones sort y (\\\\) de la librer\u00eda\n-- Data.List. \n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (sort, (\\\\))\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n (con auxiliares)\n-- ============================\n\nmayores1 :: Ord a => Int -> [[a]] -> [(a,Int)]\nmayores1 n xss = take n (reverse (sort (enumeracion xss)))\n\n-- (enumeracion xss) es la lista de los elementos de xs junto con el\n-- n\u00famero de su fila. Por ejemplo,\n--    ghci> enumeracion [[4,26,9],[2,37,53],[41,1,8]]\n--    [(4,1),(26,1),(9,1),(2,2),(37,2),(53,2),(41,3),(1,3),(8,3)]\nenumeracion :: [[a]] -> [(a,Int)]\nenumeracion xss =\n    [(x,i) | (xs,i) <- enumeracionFilas xss, x <- xs]\n\n-- (enumeracionFilas xss) es la lista de las filas de xs junto con su\n-- n\u00famero. Por ejemplo,\n--    ghci> enumeracionFilas [[4,26,9],[2,37,53],[41,1,8]]\n--    [([4,26,9],1),([2,37,53],2),([41,1,8],3)]\nenumeracionFilas :: [[a]] -> [([a],Int)]\nenumeracionFilas xss = zip xss [1..]\n\n-- 2\u00aa soluci\u00f3n (sin auxiliares)\n-- ============================\n\nmayores2 :: Ord a => Int -> [[a]] -> [(a,Int)]\nmayores2 n xss = \n    take n (reverse (sort [(x,i) | (xs,i) <- zip xss [1..], x <- xs]))\n\n-- Comprobaciones\n-- ==============\n\n-- Las dos definiciones son equivalentes\nprop_equivalencia :: Int -> [[Int]] -> Bool\nprop_equivalencia n xss =\n    mayores1 n xss == mayores2 n xss\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_equivalencia\n--    +++ OK, passed 100 tests.\n\n-- La propiedad de mayores es\nprop_mayores :: Int -> [[Int]] -> Bool\nprop_mayores n xss =\n    and [x <= y | x <- elementos \\\\ elementosMayores, y <- elementosMayores]\n    where elementos = concat xss\n          elementosMayores = [x | (x,_) <- mayores1 n xss]\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_mayores\n--    +++ OK, passed 100 tests.\n\n-- Otra forma de expresa la propiedad es\nprop_mayores2 :: Int -> [[Int]] -> Bool\nprop_mayores2 n xss = \n    all (\\x -> all (<=x) elementosRestantes) elementosMayores\n    where elementosMayores   = map fst (mayores1 n xss)\n          elementosRestantes = concat xss \\\\ elementosMayores\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_mayores2\n--    +++ OK, passed 100 tests.\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Enunciado &#8212; Las matrices se pueden representar mediante listas de listas. Por &#8212; ejemplo, la matriz &#8212; |3 2 5| &#8212; |4 9 7| &#8212; se puede representar por [[3,2,5],[4,9,7]]. &#8212; &#8212; Definir la funci\u00f3n &#8212; mayores :: Ord a => Int -> [[a]] -> [(a,Int)] &#8212; tal que (mayores n xss) es la lista&#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":[41,100,161,8,12,160,80,11,32,14,159,47,146,9],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/577"}],"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=577"}],"version-history":[{"count":8,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/577\/revisions"}],"predecessor-version":[{"id":739,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/577\/revisions\/739"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=577"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=577"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=577"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}