Clausura transitiva
Usando el tipo de las relaciones binarias, definir la función
1 |
clausuraTransitiva :: Eq a => Rel a -> Rel a |
tal que clausuraTransitiva r
es la clausura transitiva de r
; es decir, la menor relación transitiva que contiene a r. Por ejemplo,
1 2 |
λ> clausuraTransitiva (R ([1..6],[(1,2),(2,5),(5,6)])) R ([1,2,3,4,5,6],[(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)]) |
Comprobar con QuickCheck que clausuraTransitiva es transitiva.
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 |
import Relaciones_binarias (Rel(R)) import Relaciones_transitivas (transitiva) import Data.List (union) import Test.QuickCheck -- 1ª solución -- =========== clausuraTransitiva :: Ord a => Rel a -> Rel a clausuraTransitiva (R (u,g)) = R (u, aux g) where aux u' | cerradoTr u' = u' | otherwise = aux (u' `union` comp u' u') cerradoTr r = subconjunto (comp r r) r comp r s = [(x,z) | (x,y) <- r, (y',z) <- s, y == y'] subconjunto xs ys = all (`elem` ys) xs -- 2ª solución -- =========== clausuraTransitiva2 :: Ord a => Rel a -> Rel a clausuraTransitiva2 (R (u,g)) = R (u, until cerradoTr (\r -> r `union` comp r r) g) where cerradoTr r = subconjunto (comp r r) r comp r s = [(x,z) | (x,y) <- r, (y',z) <- s, y == y'] subconjunto xs ys = all (`elem` ys) xs -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_clausuraTransitiva :: Rel Int -> Bool prop_clausuraTransitiva r = clausuraTransitiva r == clausuraTransitiva2 r -- La comprobación es -- λ> quickCheck prop_clausuraTransitiva -- +++ OK, passed 100 tests. -- Propiedad -- ========= -- La propiedad es prop_clausuraTransitivaEsTransitiva :: Rel Int -> Bool prop_clausuraTransitivaEsTransitiva r = transitiva (clausuraTransitiva r) -- La función transitiva está definida en el ejercicio -- "Relaciones transitivas" que se encuentra en -- https://bit.ly/42WRPJv -- La comprobación es -- λ> quickCheck prop_clausuraTransitivaEsTransitiva -- +++ OK, passed 100 tests. |
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 |
from typing import TypeVar from hypothesis import given from hypothesis import strategies as st from src.Relaciones_binarias import Rel, relacionArbitraria from src.Relaciones_transitivas import transitiva A = TypeVar('A') # 1ª solución # =========== def clausuraTransitiva(r: Rel[A]) -> Rel[A]: (u, g) = r def subconjunto(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> bool: return set(xs) <= set(ys) def comp(r: list[tuple[A, A]], s: list[tuple[A, A]]) -> list[tuple[A, A]]: return list({(x, z) for (x, y) in r for (y1, z) in s if y == y1}) def cerradoTr(r: list[tuple[A, A]]) -> bool: return subconjunto(comp(r, r), r) def union(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> list[tuple[A, A]]: return xs + [y for y in ys if y not in xs] def aux(u1: list[tuple[A, A]]) -> list[tuple[A, A]]: if cerradoTr(u1): return u1 return aux(union(u1, comp(u1, u1))) return (u, aux(g)) # 2ª solución # =========== def clausuraTransitiva2(r: Rel[A]) -> Rel[A]: (u, g) = r def subconjunto(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> bool: return set(xs) <= set(ys) def comp(r: list[tuple[A, A]], s: list[tuple[A, A]]) -> list[tuple[A, A]]: return list({(x, z) for (x, y) in r for (y1, z) in s if y == y1}) def cerradoTr(r: list[tuple[A, A]]) -> bool: return subconjunto(comp(r, r), r) def union(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> list[tuple[A, A]]: return xs + [y for y in ys if y not in xs] def aux(u1: list[tuple[A, A]]) -> list[tuple[A, A]]: if cerradoTr(u1): return u1 return aux(union(u1, comp(u1, u1))) g1: list[tuple[A, A]] = g while not cerradoTr(g1): g1 = union(g1, comp(g1, g1)) return (u, g1) # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=0, max_value=10)) def test_clausuraTransitiva(n: int) -> None: r = relacionArbitraria(n) assert clausuraTransitiva(r) == clausuraTransitiva2(r) # Propiedad # ========= # La propiedad es @given(st.integers(min_value=0, max_value=10)) def test_cla(n: int) -> None: r = relacionArbitraria(n) assert transitiva(clausuraTransitiva(r)) # La función transitiva está definida en el ejercicio # "Relaciones transitivas" que se encuentra en # https://bit.ly/42WRPJv # La comprobación es # > poetry run pytest -q Clausura_transitiva.py # 2 passed in 0.16s |