{"id":8012,"date":"2023-04-05T06:00:09","date_gmt":"2023-04-05T04:00:09","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8012"},"modified":"2023-03-13T09:51:07","modified_gmt":"2023-03-13T07:51:07","slug":"05-abr-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/05-abr-23\/","title":{"rendered":"Relaciones transitivas"},"content":{"rendered":"<p>Usando el <a href=\"https:\/\/bit.ly\/3IVVqOT\">tipo de las relaciones binarias<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   transitiva :: Ord a => Rel a -> Bool\n<\/pre>\n<p>tal que <code>transitiva r<\/code> se verifica si la relaci\u00f3n <code>r<\/code> es transitiva. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   transitiva (R ([1,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)])) == True\n   transitiva (R ([1,3,5],[(1,1),(1,3),(3,1),(5,5)]))       == False\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport Relaciones_binarias (Rel(R))\nimport Reconocimiento_de_subconjunto (subconjunto)\nimport Universo_y_grafo_de_una_relacion_binaria (grafo)\nimport Composicion_de_relaciones_binarias_v2 (composicion)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ntransitiva1 :: Ord a => Rel a -> Bool\ntransitiva1 r@(R (_,g)) = subconjunto (grafo (composicion r r)) g\n\n-- La funci\u00f3n subconjunto est\u00e1 definida en el ejercicio\n-- \"Reconocimiento de subconjunto\" que se encuentra en\n-- https:\/\/bit.ly\/427Tyeq\n--\n-- La funci\u00f3n grafo est\u00e1 definida en el ejercicio\n-- \"Universo y grafo de una relaci\u00f3n binaria\" que se encuentra en\n-- https:\/\/bit.ly\/3J35mpC\n--\n-- La funci\u00f3n composici\u00f3n est\u00e1 definida en el ejercicio\n-- \"Composici\u00f3n de relaciones binarias\" que se encuentra en\n-- https:\/\/bit.ly\/3JyJrs7\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ntransitiva2 :: Ord a => Rel a -> Bool\ntransitiva2 (R (_,g)) = aux g\n  where\n    aux [] = True\n    aux ((x,y):g') = and [(x,z) `elem` g | (u,z) <- g, u == y] &#038;&#038; aux g'\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_transitiva :: Rel Int -> Bool\nprop_transitiva r =\n  transitiva1 r == transitiva2 r\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_transitiva\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> transitiva1 (R ([1..4001],[(x,x+1) | x <- [1..4000]]))\n--    False\n--    (3.15 secs, 898,932,776 bytes)\n--    \u03bb> transitiva2 (R ([1..4001],[(x,x+1) | x <- [1..4000]]))\n--    False\n--    (0.01 secs, 1,396,720 bytes)\n--\n--    \u03bb> transitiva1 (R ([1..60], [(x,y) | x <- [1..60], y <- [1..60]]))\n--    True\n--    (2.71 secs, 852,578,456 bytes)\n--    \u03bb> transitiva2 (R ([1..60], [(x,y) | x <- [1..60], y <- [1..60]]))\n--    True\n--    (9.13 secs, 777,080,288 bytes)\n\n-- En lo sucesivo, usaremos la 1\u00aa definici\u00f3n\ntransitiva :: Ord a => Rel a -> Bool\ntransitiva = transitiva1\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\nfrom typing import TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nfrom src.Composicion_de_relaciones_binarias_v2 import composicion\nfrom src.Reconocimiento_de_subconjunto import subconjunto\nfrom src.Relaciones_binarias import Rel, relacionArbitraria\nfrom src.Universo_y_grafo_de_una_relacion_binaria import grafo\n\nsetrecursionlimit(10**6)\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef transitiva1(r: Rel[A]) -> bool:\n    g = grafo(r)\n    return subconjunto(grafo(composicion(r, r)), g)\n\n# La funci\u00f3n subconjunto est\u00e1 definida en el ejercicio\n# \"Reconocimiento de subconjunto\" que se encuentra en\n# https:\/\/bit.ly\/427Tyeq\n#\n# La funci\u00f3n grafo est\u00e1 definida en el ejercicio\n# \"Universo y grafo de una relaci\u00f3n binaria\" que se encuentra en\n# https:\/\/bit.ly\/3J35mpC\n#\n# La funci\u00f3n composici\u00f3n est\u00e1 definida en el ejercicio\n# \"Composici\u00f3n de relaciones binarias\" que se encuentra en\n# https:\/\/bit.ly\/3JyJrs7\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef transitiva2(r: Rel[A]) -> bool:\n    g = grafo(r)\n    def aux(g1: list[tuple[A,A]]) -> bool:\n        if not g1:\n            return True\n        (x, y) = g1[0]\n        return all(((x, z) in g for (u,z) in g if u == y)) and aux(g1[1:])\n\n    return aux(g)\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef transitiva3(r: Rel[A]) -> bool:\n    g = grafo(r)\n    g1 = list(g)\n    for (x, y) in g1:\n        if not all(((x, z) in g for (u,z) in g if u == y)):\n            return False\n    return True\n\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=0, max_value=10))\ndef test_simetrica(n: int) -> None:\n    r = relacionArbitraria(n)\n    res = transitiva1(r)\n    assert transitiva2(r) == res\n    assert transitiva3(r) == res\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -q Relaciones_transitivas.py\n#    1 passed in 0.12s\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> u1 = range(6001)\n#    >>> g1 = [(x, x+1) for x in range(6000)]\n#    >>> tiempo(\"transitiva1((u1, g1))\")\n#    1.04 segundos\n#    >>> tiempo(\"transitiva2((u1, g1))\")\n#    0.00 segundos\n#    >>> tiempo(\"transitiva3((u1, g1))\")\n#    0.00 segundos\n#\n#    >>> u2 = range(60)\n#    >>> g2 = [(x, y) for x in u2 for y in u2]\n#    >>> tiempo(\"transitiva1((u2, g2))\")\n#    0.42 segundos\n#    >>> tiempo(\"transitiva2((u2, g2))\")\n#    5.24 segundos\n#    >>> tiempo(\"transitiva3((u2, g2))\")\n#    4.83 segundos\n\n# En lo sucesivo usaremos la 1\u00aa definici\u00f3n\ntransitiva = transitiva1\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Usando el tipo de las relaciones binarias, definir la funci\u00f3n transitiva :: Ord a => Rel a -> Bool tal que transitiva r se verifica si la relaci\u00f3n r es transitiva. Por ejemplo, transitiva (R ([1,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)])) == True transitiva (R ([1,3,5],[(1,1),(1,3),(3,1),(5,5)])) == False Soluciones A continuaci\u00f3n se muestran las soluciones en Haskell y las soluciones&#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":[581],"tags":[576],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8012"}],"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=8012"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8012\/revisions"}],"predecessor-version":[{"id":8013,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8012\/revisions\/8013"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8012"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8012"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8012"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}