{"id":7079,"date":"2022-06-09T06:00:10","date_gmt":"2022-06-09T04:00:10","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7079"},"modified":"2022-06-06T11:15:52","modified_gmt":"2022-06-06T09:15:52","slug":"representacion-matricial-de-relaciones-binarias","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/representacion-matricial-de-relaciones-binarias\/","title":{"rendered":"Representaci\u00f3n matricial de relaciones binarias"},"content":{"rendered":"<p>Dada una relaci\u00f3n <code>r<\/code> sobre un conjunto de n\u00fameros enteros, la matriz asociada a <code>r<\/code> es una matriz booleana <code>p<\/code> (cuyos elementos son <code>True<\/code> o <code>False<\/code>), tal que <code>p(i,j) = True<\/code> si y s\u00f3lo si <code>i<\/code> est\u00e1 relacionado con <code>j<\/code> mediante la relaci\u00f3n <code>r<\/code>.<\/p>\n<p>Las relaciones binarias homog\u00e9neas y las matrices booleanas se pueden representar por<\/p>\n<pre lang=\"text\">\n   type Relacion = ([Int],[(Int,Int)])\n   type Matriz = Array (Int,Int) Bool\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   matrizRB:: Relacion -> Matriz\n<\/pre>\n<p>tal que <code>(matrizRB r)<\/code> es la matriz booleana asociada a <code>r<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> matrizRB ([1..3],[(1,1), (1,3), (3,1), (3,3)])\n   array ((1,1),(3,3)) [((1,1),True) ,((1,2),False),((1,3),True),\n                        ((2,1),False),((2,2),False),((2,3),False),\n                        ((3,1),True) ,((3,2),False),((3,3),True)]\n   \u03bb> matrizRB ([1..3],[(1,3), (3,1)])\n   array ((1,1),(3,3)) [((1,1),False),((1,2),False),((1,3),True),\n                        ((2,1),False),((2,2),False),((2,3),False),\n                        ((3,1),True) ,((3,2),False),((3,3),False)]\n   \u03bb> let n = 10^4 in matrizRB3 ([1..n],[(1,n),(n,1)]) ! (n,n)\n   False\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.Array      (Array, accumArray, array, listArray)\nimport Test.QuickCheck (Arbitrary, Gen, arbitrary, sublistOf, suchThat,\n                        quickCheck)\n\ntype Relacion = ([Int],[(Int,Int)])\ntype Matriz   = Array (Int,Int) Bool\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nmatrizRB1 :: Relacion -> Matriz \nmatrizRB1 r = \n    array ((1,1),(n,n)) \n          [((a,b), (a,b) `elem` grafo r) | a <- [1..n], b <- [1..n]]\n    where n = maximum (universo r)\n          universo (us,_) = us\n          grafo (_,ps)    = ps\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nmatrizRB2 :: Relacion -> Matriz\nmatrizRB2 r = \n    listArray ((1,1),(n,n)) \n              [(a,b) `elem` snd r | a <- [1..n], b <- [1..n]]\n    where n = maximum (fst r)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nmatrizRB3 :: Relacion -> Matriz\nmatrizRB3 r = \n    accumArray (||) False ((1,1),(n,n)) (zip (snd r) (repeat True))\n    where n = maximum (fst r)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- Tipo de relaciones binarias\nnewtype RB = RB Relacion\n  deriving Show\n\n-- relacionArbitraria genera una relaci\u00f3n arbitraria. Por ejemplo, \n--    \u03bb> generate relacionArbitraria\n--    RB ([1,2,3,4,5],[(1,4),(1,5),(2,3),(2,4),(4,2),(4,3),(4,4),(5,1),(5,2),(5,3),(5,4)])\nrelacionArbitraria :: Gen RB\nrelacionArbitraria = do\n  n <- arbitrary `suchThat` (> 1)\n  xs <- sublistOf [(x,y) | x <- [1..n], y <- [1..n]]\n  return (RB ([1..n], xs))\n\n-- RB es una subclase de Arbitrary\ninstance Arbitrary RB where\n  arbitrary = relacionArbitraria\n\n-- La propiedad es\nprop_matrizRB :: RB -> Bool\nprop_matrizRB (RB r) =\n  all (== matrizRB1 r)\n      [matrizRB2 r,\n       matrizRB3 r]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_matrixzB\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> let n = 2000 in matrizRB1 ([1..n],[(1,n),(n,1)]) ! (n,n)\n--    False\n--    (2.02 secs, 1,505,248,912 bytes)\n--    \u03bb> let n = 2000 in matrizRB2 ([1..n],[(1,n),(n,1)]) ! (n,n)\n--    False\n--    (1.92 secs, 833,232,360 bytes)\n--    \u03bb> let n = 2000 in matrizRB3 ([1..n],[(1,n),(n,1)]) ! (n,n)\n--    False\n--    (0.05 secs, 32,848,696 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Representacion_matricial_de_relaciones_binarias.hs\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Dada una relaci\u00f3n r sobre un conjunto de n\u00fameros enteros, la matriz asociada a r es una matriz booleana p (cuyos elementos son True o False), tal que p(i,j) = True si y s\u00f3lo si i est\u00e1 relacionado con j mediante la relaci\u00f3n r. Las relaciones binarias homog\u00e9neas y las matrices booleanas se pueden representar&#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":[2],"tags":[569,576],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7079"}],"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=7079"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7079\/revisions"}],"predecessor-version":[{"id":7080,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7079\/revisions\/7080"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7079"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7079"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7079"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}