Relaciones transitivas
Usando el tipo de las relaciones binarias, definir la función
|
1 |
transitiva :: Ord a => Rel a -> Bool |
tal que transitiva r se verifica si la relación r es transitiva. Por ejemplo,
|
1 2 |
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ón se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
import Relaciones_binarias (Rel(R)) import Reconocimiento_de_subconjunto (subconjunto) import Universo_y_grafo_de_una_relacion_binaria (grafo) import Composicion_de_relaciones_binarias_v2 (composicion) import Test.QuickCheck -- 1ª solución -- =========== transitiva1 :: Ord a => Rel a -> Bool transitiva1 r@(R (_,g)) = subconjunto (grafo (composicion r r)) g -- La función subconjunto está definida en el ejercicio -- "Reconocimiento de subconjunto" que se encuentra en -- https://bit.ly/427Tyeq -- -- La función grafo está definida en el ejercicio -- "Universo y grafo de una relación binaria" que se encuentra en -- https://bit.ly/3J35mpC -- -- La función composición está definida en el ejercicio -- "Composición de relaciones binarias" que se encuentra en -- https://bit.ly/3JyJrs7 -- 2ª solución -- =========== transitiva2 :: Ord a => Rel a -> Bool transitiva2 (R (_,g)) = aux g where aux [] = True aux ((x,y):g') = and [(x,z) `elem` g | (u,z) <- g, u == y] && aux g' -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_transitiva :: Rel Int -> Bool prop_transitiva r = transitiva1 r == transitiva2 r -- La comprobación es -- λ> quickCheck prop_transitiva -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> transitiva1 (R ([1..4001],[(x,x+1) | x <- [1..4000]])) -- False -- (3.15 secs, 898,932,776 bytes) -- λ> transitiva2 (R ([1..4001],[(x,x+1) | x <- [1..4000]])) -- False -- (0.01 secs, 1,396,720 bytes) -- -- λ> transitiva1 (R ([1..60], [(x,y) | x <- [1..60], y <- [1..60]])) -- True -- (2.71 secs, 852,578,456 bytes) -- λ> transitiva2 (R ([1..60], [(x,y) | x <- [1..60], y <- [1..60]])) -- True -- (9.13 secs, 777,080,288 bytes) -- En lo sucesivo, usaremos la 1ª definición transitiva :: Ord a => Rel a -> Bool transitiva = transitiva1 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
from sys import setrecursionlimit from timeit import Timer, default_timer from typing import TypeVar from hypothesis import given from hypothesis import strategies as st from src.Composicion_de_relaciones_binarias_v2 import composicion from src.Reconocimiento_de_subconjunto import subconjunto from src.Relaciones_binarias import Rel, relacionArbitraria from src.Universo_y_grafo_de_una_relacion_binaria import grafo setrecursionlimit(10**6) A = TypeVar('A') # 1ª solución # =========== def transitiva1(r: Rel[A]) -> bool: g = grafo(r) return subconjunto(grafo(composicion(r, r)), g) # La función subconjunto está definida en el ejercicio # "Reconocimiento de subconjunto" que se encuentra en # https://bit.ly/427Tyeq # # La función grafo está definida en el ejercicio # "Universo y grafo de una relación binaria" que se encuentra en # https://bit.ly/3J35mpC # # La función composición está definida en el ejercicio # "Composición de relaciones binarias" que se encuentra en # https://bit.ly/3JyJrs7 # 2ª solución # =========== def transitiva2(r: Rel[A]) -> bool: g = grafo(r) def aux(g1: list[tuple[A,A]]) -> bool: if not g1: return True (x, y) = g1[0] return all(((x, z) in g for (u,z) in g if u == y)) and aux(g1[1:]) return aux(g) # 3ª solución # =========== def transitiva3(r: Rel[A]) -> bool: g = grafo(r) g1 = list(g) for (x, y) in g1: if not all(((x, z) in g for (u,z) in g if u == y)): return False return True # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=0, max_value=10)) def test_simetrica(n: int) -> None: r = relacionArbitraria(n) res = transitiva1(r) assert transitiva2(r) == res assert transitiva3(r) == res # La comprobación es # > poetry run pytest -q Relaciones_transitivas.py # 1 passed in 0.12s # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> u1 = range(6001) # >>> g1 = [(x, x+1) for x in range(6000)] # >>> tiempo("transitiva1((u1, g1))") # 1.04 segundos # >>> tiempo("transitiva2((u1, g1))") # 0.00 segundos # >>> tiempo("transitiva3((u1, g1))") # 0.00 segundos # # >>> u2 = range(60) # >>> g2 = [(x, y) for x in u2 for y in u2] # >>> tiempo("transitiva1((u2, g2))") # 0.42 segundos # >>> tiempo("transitiva2((u2, g2))") # 5.24 segundos # >>> tiempo("transitiva3((u2, g2))") # 4.83 segundos # En lo sucesivo usaremos la 1ª definición transitiva = transitiva1 |