{"id":7997,"date":"2023-03-28T06:00:18","date_gmt":"2023-03-28T04:00:18","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7997"},"modified":"2023-03-11T09:48:47","modified_gmt":"2023-03-11T07:48:47","slug":"28-mar-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/28-mar-23\/","title":{"rendered":"Relaciones binarias"},"content":{"rendered":"

Una relaci\u00f3n binaria R sobre un conjunto A se puede mediante un par (u,g) donde u es la lista de los elementos de tipo A (el universo de R) y g es la lista de pares de elementos de u (el grafo de R).<\/p>\n

Definir el tipo de dato (Rel a), para representar las relaciones binarias sobre a, y la funci\u00f3n<\/p>\n

\n   esRelacionBinaria :: Eq a => Rel a -> Bool\n<\/pre>\n
tal que esRelacionBinaria r<\/code> se verifica si r<\/code> es una relaci\u00f3n binaria. Por ejemplo,<\/p>\n
\n   \u03bb> esRelacionBinaria (R ([1, 3], [(3, 1), (3, 3)]))\n   True\n   \u03bb> esRelacionBinaria (R ([1, 3], [(3, 1), (3, 2)]))\n   False\n<\/pre>\n
Adem\u00e1s, definir un generador de relaciones binarias y comprobar que las relaciones que genera son relaciones binarias.<\/p>\n
Soluciones<\/b><\/p>\n
A continuaci\u00f3n se muestran las soluciones en Haskell<\/a> y las soluciones en Python<\/a>.<\/p>\n
<\/a>
\nSoluciones en Haskell<\/b><\/p>\n
\nimport Data.List (nub)\nimport Test.QuickCheck\n\nnewtype Rel a = R ([a], [(a,a)])\n  deriving (Eq, Show)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nesRelacionBinaria :: Eq a => Rel a -> Bool\nesRelacionBinaria (R (u, g)) =\n  and [x `elem` u && y `elem` u | (x,y) <- g]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nesRelacionBinaria2 :: Eq a => Rel a -> Bool\nesRelacionBinaria2 (R (u, g)) =\n  all (\\(x,y) -> x `elem` u && y `elem` u) g\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nesRelacionBinaria3 :: Eq a => Rel a -> Bool\nesRelacionBinaria3 (R (_, []))         = True\nesRelacionBinaria3 (R (u, (x,y):g)) =\n  x `elem` u &&\n  y `elem` u &&\n  esRelacionBinaria3 (R (u, g))\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- Generador de relaciones binarias. Por ejemplo,\n--    \u03bb> sample (relacionArbitraria :: Gen (Rel Int))\n--    R ([0],[])\n--    R ([0,-1,1],[(0,-1),(0,1),(-1,1),(1,0)])\n--    R ([1],[])\n--    R ([-5,3],[(-5,-5),(-5,3),(3,-5),(3,3)])\n--    R ([-2,-7],[(-7,-7)])\n--    R ([11,-7],[])\n--    R ([0],[])\n--    R ([-13,-11],[(-13,-13)])\nrelacionArbitraria :: (Arbitrary a, Eq a) => Gen (Rel a)\nrelacionArbitraria = do\n  n <- choose (0, 10)\n  u1 <- vectorOf n arbitrary\n  let u = nub u1\n  g <- sublistOf [(x,y) | x <- u, y <- u]\n  return (R (u, g))\n\n-- Relaciones es una subclase de Arbitrary.\ninstance (Arbitrary a, Eq a) => Arbitrary (Rel a) where\n  arbitrary = relacionArbitraria\n\n-- La propiedad es\nprop_esRelacionBinaria :: Rel Int -> Bool\nprop_esRelacionBinaria r =\n  esRelacionBinaria r  &&\n  esRelacionBinaria2 r &&\n  esRelacionBinaria3 r\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_esRelacionBinaria\n--    +++ OK, passed 100 tests.\n<\/pre>\n
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\nfrom random import choice, randint, sample\nfrom typing import TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nA = TypeVar('A')\n\nRel = tuple[list[A], list[tuple[A, A]]]\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef esRelacionBinaria(r: Rel[A]) -> bool:\n    (u, g) = r\n    return all((x in u and y in u for (x, y) in g))\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef esRelacionBinaria2(r: Rel[A]) -> bool:\n    (u, g) = r\n    if not g:\n        return True\n    (x, y) = g[0]\n    return x in u and y in u and esRelacionBinaria2((u, g[1:]))\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef esRelacionBinaria3(r: Rel[A]) -> bool:\n    (u, g) = r\n    for (x, y) in g:\n        if x not in u or y not in u:\n            return False\n    return True\n\n# Generador de relaciones binarias\n# ================================\n\n# conjuntoArbitrario(n) es un conjunto arbitrario cuyos elementos est\u00e1n\n# entre 0 y n-1. Por ejemplo,\n#    >>> conjuntoArbitrario(10)\n#    [8, 9, 4, 5]\n#    >>> conjuntoArbitrario(10)\n#    [1, 2, 3, 4, 5, 6, 7, 8, 9]\n#    >>> conjuntoArbitrario(10)\n#    [0, 1, 2, 3, 6, 7, 9]\n#    >>> conjuntoArbitrario(10)\n#    [8, 2, 3, 7]\ndef conjuntoArbitrario(n: int) -> list[int]:\n    xs = sample(range(n), randint(0, n))\n    return list(set(xs))\n\n# productoCartesiano(xs, ys) es el producto cartesiano de xs e ys. Por\n# ejemplo,\n#    >>> productoCartesiano([2, 3], [1, 7, 5])\n#    [(2, 1), (2, 7), (2, 5), (3, 1), (3, 7), (3, 5)]\ndef productoCartesiano(xs: list[int], ys: list[int]) -> list[tuple[int, int]]:\n    return [(x, y) for x in xs for y in ys]\n\n# sublistaArbitraria(xs) es una sublista arbitraria de xs. Por ejemplo,\n#    >>> sublistaArbitraria(range(10))\n#    [3, 7]\n#    >>> sublistaArbitraria(range(10))\n#    []\n#    >>> sublistaArbitraria(range(10))\n#    [4, 1, 0, 9, 8, 7, 5, 6, 2, 3]\ndef sublistaArbitraria(xs: list[A]) -> list[A]:\n    n = len(xs)\n    k = randint(0, n)\n    return sample(xs, k)\n\n# relacionArbitraria(n) es una relaci\u00f3n arbitraria tal que los elementos\n# de su universo est\u00e1n entre 0 y n-1. Por ejemplo,\n#    >>> relacionArbitraria(3)\n#    ([0, 1], [(1, 0), (1, 1)])\n#    >>> relacionArbitraria(3)\n#    ([], [])\n#    >>> relacionArbitraria(5)\n#    ([0, 2, 3, 4], [(2, 0), (3, 3), (2, 3), (4, 0), (3, 4), (4, 2)])\ndef relacionArbitraria(n: int) -> Rel[int]:\n    u = conjuntoArbitrario(n)\n    g = sublistaArbitraria(productoCartesiano(u, u))\n    return (u, g)\n\n# Comprobaci\u00f3n de la propiedad\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=0, max_value=10))\ndef test_esRelacionBinaria(n: int) -> None:\n    r = relacionArbitraria(n)\n    assert esRelacionBinaria(r)\n    assert esRelacionBinaria2(r)\n    assert esRelacionBinaria3(r)\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -q Relaciones_binarias.py\n#    1 passed in 0.14s\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Una relaci\u00f3n binaria R sobre un conjunto A se puede mediante un par (u,g) donde u es la lista de los elementos de tipo A (el universo de R) y g es la lista de pares de elementos de u (el grafo de R). Definir el tipo de dato (Rel a), para representar las relaciones…<\/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\/7997"}],"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=7997"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7997\/revisions"}],"predecessor-version":[{"id":8006,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7997\/revisions\/8006"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7997"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7997"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7997"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}