Estas dos últimas semanas he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. Composición de relaciones binarias
- 2. Reconocimiento de subconjunto
- 3. Relaciones transitivas
- 4. Relaciones de equivalencia
- 5. Relaciones irreflexivas
- 6. Relaciones antisimétricas
- 7. Relaciones totales
- 8. Clausura reflexiva
- 9. Clausura simétrica
- 10. Clausura transitiva
A continuación se muestran las soluciones.
1. Composición de relaciones binarias
Usando el tipo de las relaciones binarias, definir la función
composicion :: Eq a => Rel a -> Rel a -> Rel a |
tal que composicion r s es la composición de las relaciones r y s. Por ejemplo,
λ> composicion (R ([1,2],[(1,2),(2,2)])) (R ([1,2],[(2,1)])) R ([1,2],[(1,1),(2,1)]) |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
import Relaciones_binarias (Rel(R)) import Test.QuickCheck -- 1ª solución -- =========== composicion :: Eq a => Rel a -> Rel a -> Rel a composicion (R (u1,g1)) (R (_,g2)) = R (u1,[(x,z) | (x,y) <- g1, (y',z) <- g2, y == y']) -- 2ª solución -- =========== composicion2 :: Eq a => Rel a -> Rel a -> Rel a composicion2 (R (u1,g1)) (R (_,g2)) = R (u1, aux g1) where aux [] = [] aux ((x,y):g1') = [(x,z) | (y',z) <- g2, y == y'] ++ aux g1' -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_composicion :: Rel Int -> Rel Int -> Bool prop_composicion r1 r2 = composicion r1 r2 == composicion2 r1 r2 -- La comprobación es -- λ> quickCheck prop_composicion -- +++ OK, passed 100 tests. |
from typing import TypeVar from hypothesis import given from hypothesis import strategies as st from src.Relaciones_binarias import Rel, relacionArbitraria A = TypeVar('A') # 1ª solución # =========== def composicion(r1: Rel[A], r2: Rel[A]) -> Rel[A]: (u1, g1) = r1 (_, g2) = r2 return (u1, [(x, z) for (x, y) in g1 for (u, z) in g2 if y == u]) # 2ª solución # =========== def composicion2(r1: Rel[A], r2: Rel[A]) -> Rel[A]: (u1, g1) = r1 (_, g2) = r2 def aux(g: list[tuple[A, A]]) -> list[tuple[A, A]]: if not g: return [] (x, y) = g[0] return [(x, z) for (u, z) in g2 if y == u] + aux(g[1:]) return (u1, aux(g1)) # 2ª solución # =========== def composicion3(r1: Rel[A], r2: Rel[A]) -> Rel[A]: (u1, g1) = r1 (_, g2) = r2 r: list[tuple[A, A]] = [] for (x, y) in g1: r = r + [(x, z) for (u, z) in g2 if y == u] return (u1, r) # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=0, max_value=10), st.integers(min_value=0, max_value=10)) def test_simetrica(n: int, m: int) -> None: r1 = relacionArbitraria(n) r2 = relacionArbitraria(m) res = composicion(r1, r2) assert composicion2(r1, r2) == res assert composicion2(r1, r2) == res # La comprobación es # > poetry run pytest -q Composicion_de_relaciones_binarias_v2.py # 1 passed in 0.19s |
2. Reconocimiento de subconjunto
Definir la función
subconjunto :: Ord a => [a] -> [a] -> Bool |
tal que subconjunto xs ys se verifica si xs es un subconjunto de ys. Por ejemplo,
subconjunto [3,2,3] [2,5,3,5] == True subconjunto [3,2,3] [2,5,6,5] == False |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
module Reconocimiento_de_subconjunto where import Data.List (nub, sort) import Data.Set (fromList, isSubsetOf) import Test.QuickCheck -- 1ª solución -- =========== subconjunto1 :: Ord a => [a] -> [a] -> Bool subconjunto1 xs ys = [x | x <- xs, x `elem` ys] == xs -- 2ª solución -- =========== subconjunto2 :: Ord a => [a] -> [a] -> Bool subconjunto2 [] _ = True subconjunto2 (x:xs) ys = x `elem` ys && subconjunto2 xs ys -- 3ª solución -- =========== subconjunto3 :: Ord a => [a] -> [a] -> Bool subconjunto3 xs ys = all (`elem` ys) xs -- 4ª solución -- =========== subconjunto4 :: Ord a => [a] -> [a] -> Bool subconjunto4 xs ys = fromList xs `isSubsetOf` fromList ys -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_subconjunto :: [Int] -> [Int] -> Bool prop_subconjunto xs ys = all (== subconjunto1 xs ys) [subconjunto2 xs ys, subconjunto3 xs ys, subconjunto4 xs ys] -- La comprobación es -- λ> quickCheck prop_subconjunto -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> subconjunto1 [1..2*10^4] [1..2*10^4] -- True -- (1.81 secs, 5,992,448 bytes) -- λ> subconjunto2 [1..2*10^4] [1..2*10^4] -- True -- (1.83 secs, 6,952,200 bytes) -- λ> subconjunto3 [1..2*10^4] [1..2*10^4] -- True -- (1.75 secs, 4,712,304 bytes) -- λ> subconjunto4 [1..2*10^4] [1..2*10^4] -- True -- (0.04 secs, 6,312,056 bytes) -- En lo sucesivo, usaremos la 4ª definición subconjunto :: Ord a => [a] -> [a] -> Bool subconjunto = subconjunto4 |
from sys import setrecursionlimit from timeit import Timer, default_timer from typing import TypeVar from hypothesis import given from hypothesis import strategies as st setrecursionlimit(10**6) A = TypeVar('A') # 1ª solución # =========== def subconjunto1(xs: list[A], ys: list[A]) -> bool: return [x for x in xs if x in ys] == xs # 2ª solución # =========== def subconjunto2(xs: list[A], ys: list[A]) -> bool: if not xs: return True return xs[0] in ys and subconjunto2(xs[1:], ys) # 3ª solución # =========== def subconjunto3(xs: list[A], ys: list[A]) -> bool: return all(elem in ys for elem in xs) # 4ª solución # =========== def subconjunto4(xs: list[A], ys: list[A]) -> bool: return set(xs) <= set(ys) # Comprobación de equivalencia # ============================ # La propiedad es @given(st.lists(st.integers()), st.lists(st.integers())) def test_filtraAplica(xs: list[int], ys: list[int]) -> None: r = subconjunto1(xs, ys) assert subconjunto2(xs, ys) == r assert subconjunto3(xs, ys) == r assert subconjunto4(xs, ys) == r # La comprobación es # src> poetry run pytest -q Reconocimiento_de_subconjunto.py # 1 passed in 0.31s # 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 # >>> xs = list(range(2*10**4)) # >>> tiempo("subconjunto1(xs, xs)") # 1.15 segundos # >>> tiempo("subconjunto2(xs, xs)") # 2.27 segundos # >>> tiempo("subconjunto3(xs, xs)") # 1.14 segundos # >>> tiempo("subconjunto4(xs, xs)") # 0.00 segundos # En lo sucesivo usaremos la cuarta definición subconjunto = subconjunto4 |
3. Relaciones transitivas
Usando el tipo de las relaciones binarias, definir la función
transitiva :: Ord a => Rel a -> Bool |
tal que transitiva r se verifica si la relación 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ón se muestran las soluciones en Haskell y las soluciones en Python.
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 |
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 |
4. Relaciones de equivalencia
Usando el tipo de las relaciones binarias, definir la función
esEquivalencia :: Ord a => Rel a -> Bool |
tal que esEquivalencia r se verifica si la relación r es de equivalencia. Por ejemplo,
λ> esEquivalencia (R ([1,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)])) True λ> esEquivalencia (R ([1,2,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)])) False λ> esEquivalencia (R ([1,3,5],[(1,1),(1,3),(3,3),(5,5)])) False |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
import Relaciones_binarias (Rel(R)) import Relaciones_reflexivas (reflexiva) import Relaciones_simetricas (simetrica) import Relaciones_transitivas (transitiva) esEquivalencia :: Ord a => Rel a -> Bool esEquivalencia r = reflexiva r && simetrica r && transitiva r |
from typing import TypeVar from src.Relaciones_binarias import Rel, relacionArbitraria from src.Relaciones_reflexivas import reflexiva from src.Relaciones_simetricas import simetrica from src.Relaciones_transitivas import transitiva A = TypeVar('A') def esEquivalencia(r: Rel[A]) -> bool: return reflexiva(r) and simetrica(r) and transitiva(r) |
5. Relaciones irreflexivas
Usando el tipo de las relaciones binarias, definir la función
irreflexiva :: Eq a => Rel a -> Bool |
tal que irreflexiva r se verifica si la relación r es irreflexiva; es decir, si ningún elemento de su universo está relacionado con él mismo. Por ejemplo,
irreflexiva (R ([1,2,3],[(1,2),(2,1),(2,3)])) == True irreflexiva (R ([1,2,3],[(1,2),(2,1),(3,3)])) == False |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
import Relaciones_binarias (Rel(R)) import Test.QuickCheck -- 1ª solución -- =========== irreflexiva :: Eq a => Rel a -> Bool irreflexiva (R (u,g)) = and [(x,x) `notElem` g | x <- u] -- 2ª solución -- =========== irreflexiva2 :: Eq a => Rel a -> Bool irreflexiva2 (R(u,g)) = all (\x -> (x,x) `notElem` g) u -- 3ª solución -- =========== irreflexiva3 :: Eq a => Rel a -> Bool irreflexiva3 (R(u,g)) = aux u where aux [] = True aux (x:xs) = (x,x) `notElem` g && aux xs -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_irreflexiva :: Rel Int -> Bool prop_irreflexiva r = all (== irreflexiva r) [irreflexiva2 r, irreflexiva3 r] -- La comprobación es -- λ> quickCheck prop_irreflexiva -- +++ OK, passed 100 tests. |
from typing import TypeVar from hypothesis import given from hypothesis import strategies as st from src.Relaciones_binarias import Rel, relacionArbitraria A = TypeVar('A') # 1ª solución # =========== def irreflexiva(r: Rel[A]) -> bool: (u, g) = r return all(((x, x) not in g for x in u)) # 2ª solución # =========== def irreflexiva2(r: Rel[A]) -> bool: (u, g) = r def aux(xs: list[A]) -> bool: if not xs: return True return (xs[0], xs[0]) not in g and aux(xs[1:]) return aux(u) # 3ª solución # =========== def irreflexiva3(r: Rel[A]) -> bool: (u, g) = r for x in u: if (x, x) in g: return False return True # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=0, max_value=10)) def test_irreflexiva(n: int) -> None: r = relacionArbitraria(n) res = irreflexiva(r) assert irreflexiva2(r) == res assert irreflexiva3(r) == res # La comprobación es # > poetry run pytest -q Relaciones_irreflexivas.py # 1 passed in 0.12s |
6. Relaciones antisimétricas
Usando el tipo de las relaciones binarias, definir la función
antisimetrica :: Eq a => Rel a -> Bool |
tal que antisimetrica r se verifica si la relación r es antisimétrica; es decir, si (x,y) e (y,x) están relacionado, entonces x=y. Por ejemplo,
antisimetrica (R ([1,2],[(1,2)])) == True antisimetrica (R ([1,2],[(1,2),(2,1)])) == False antisimetrica (R ([1,2],[(1,1),(2,1)])) == True |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
import Relaciones_binarias (Rel(R)) import Test.QuickCheck -- 1ª solución -- =========== antisimetrica :: Eq a => Rel a -> Bool antisimetrica (R (_,g)) = null [(x,y) | (x,y) <- g, x /= y, (y,x) `elem` g] -- 2ª solución -- =========== antisimetrica2 :: Eq a => Rel a -> Bool antisimetrica2 (R (_,g)) = and [(y,x) `notElem` g | (x,y) <- g, x /= y] -- 3ª solución -- =========== antisimetrica3 :: Eq a => Rel a -> Bool antisimetrica3 (R (_,g)) = all (\(x, y) -> (y,x) `notElem` g || x == y) g -- 4ª solución -- =========== antisimetrica4 :: Eq a => Rel a -> Bool antisimetrica4 (R (u,g)) = and [((x,y) `elem` g && (y,x) `elem` g) --> (x == y) | x <- u, y <- u] where p --> q = not p || q -- 5ª solución -- =========== antisimetrica5 :: Eq a => Rel a -> Bool antisimetrica5 (R (_,g)) = aux g where aux [] = True aux ((x,y):g') = ((y,x) `notElem` g || x == y) && aux g' -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_antisimetrica :: Rel Int -> Bool prop_antisimetrica r = all (== antisimetrica r) [antisimetrica2 r, antisimetrica3 r, antisimetrica4 r, antisimetrica5 r] -- La comprobación es -- λ> quickCheck prop_antisimetrica -- +++ OK, passed 100 tests. |
from typing import TypeVar from hypothesis import given from hypothesis import strategies as st from src.Relaciones_binarias import Rel, relacionArbitraria A = TypeVar('A') # 1ª solución # =========== def antisimetrica(r: Rel[A]) -> bool: (u, g) = r return [(x, y) for (x, y) in g if x != y and (y, x) in g] == [] # 2ª solución # =========== def antisimetrica2(r: Rel[A]) -> bool: (u, g) = r return all(((y, x) not in g for (x, y) in g if x != y)) # 3ª solución # =========== def antisimetrica3(r: Rel[A]) -> bool: (u, g) = r return all ((not ((x, y) in g and (y, x) in g) or x == y for x in u for y in u)) # 4ª solución # =========== def antisimetrica4(r: Rel[A]) -> bool: (u, g) = r def aux(xys: list[tuple[A, A]]) -> bool: if not xys: return True (x, y) = xys[0] return ((y, x) not in g or x == y) and aux(xys[1:]) return aux(g) # 5ª solución # =========== def antisimetrica5(r: Rel[A]) -> bool: (u, g) = r for (x, y) in g: if (y, x) in g and x != y: return False return True # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=0, max_value=10)) def test_antisimetrica(n: int) -> None: r = relacionArbitraria(n) res = antisimetrica(r) assert antisimetrica2(r) == res assert antisimetrica3(r) == res assert antisimetrica4(r) == res assert antisimetrica5(r) == res # La comprobación es # > poetry run pytest -q Relaciones_antisimetricas.py # 1 passed in 0.13s |
7. Relaciones totales
Usando el tipo de las relaciones binarias, definir la función
total :: Eq a => Rel a -> Bool |
tal que total r se verifica si la relación r es total; es decir, si para cualquier par x, y de elementos del universo de r, se tiene que x está relacionado con y o y está relacionado con x. Por ejemplo,
total (R ([1,3],[(1,1),(3,1),(3,3)])) == True total (R ([1,3],[(1,1),(3,1)])) == False total (R ([1,3],[(1,1),(3,3)])) == False |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
import Relaciones_binarias (Rel(R)) import Test.QuickCheck (quickCheck) -- 1ª solución -- =========== total :: Eq a => Rel a -> Bool total (R (u,g)) = and [(x,y) `elem` g || (y,x) `elem` g | x <- u, y <- u] -- 2ª solución -- =========== total2 :: Eq a => Rel a -> Bool total2 (R (u,g)) = all (relacionados g) (producto u u) -- (producto xs ys) es el producto cartesiano de xs e ys. Por ejemplo, -- λ> producto [2,5] [1,4,6] -- [(2,1),(2,4),(2,6),(5,1),(5,4),(5,6)] producto :: [a] -> [a] -> [(a,a)] producto xs ys = [(x,y) | x <- xs, y <- ys] -- (relacionados g (x,y)) se verifica si los elementos x e y están -- relacionados por la relación de grafo g. Por ejemplo, -- relacionados [(2,3),(3,1)] (2,3) == True -- relacionados [(2,3),(3,1)] (3,2) == True -- relacionados [(2,3),(3,1)] (1,2) == False relacionados :: Eq a => [(a,a)] -> (a,a) -> Bool relacionados g (x,y) = (x,y) `elem` g || (y,x) `elem` g -- 3ª solución -- =========== total3 :: Eq a => Rel a -> Bool total3 (R (u,g)) = aux1 u where aux1 [] = True aux1 (x:xs) = aux2 x u && aux1 xs aux2 _ [] = True aux2 x (y:ys) = relacionados g (x,y) && aux2 x ys -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_total :: Rel Int -> Bool prop_total r = all (== total r) [total2 r, total3 r] -- La comprobación es -- λ> quickCheck prop_total -- +++ OK, passed 100 tests. |
from typing import TypeVar from hypothesis import given from hypothesis import strategies as st from src.Relaciones_binarias import Rel, relacionArbitraria A = TypeVar('A') # 1ª solución # =========== def total(r: Rel[A]) -> bool: (u, g) = r return all(((x, y) in g or (y, x) in g for x in u for y in u)) # 2ª solución # =========== # producto(xs, ys) es el producto cartesiano de xs e ys. Por ejemplo, # >>> producto([2, 5], [1, 4, 6]) # [(2, 1), (2, 4), (2, 6), (5, 1), (5, 4), (5, 6)] def producto(xs: list[A], ys: list[A]) -> list[tuple[A,A]]: return [(x, y) for x in xs for y in ys] # relacionados(g, (x, y)) se verifica si los elementos x e y están # relacionados por la relación de grafo g. Por ejemplo, # relacionados([(2, 3), (3, 1)], (2, 3)) == True # relacionados([(2, 3), (3, 1)], (3, 2)) == True # relacionados([(2, 3), (3, 1)], (1, 2)) == False def relacionados(g: list[tuple[A,A]], p: tuple[A,A]) -> bool: (x, y) = p return (x, y) in g or (y, x) in g def total2(r: Rel[A]) -> bool: (u, g) = r return all(relacionados(g, p) for p in producto(u, u)) # 3ª solución # =========== def total3(r: Rel[A]) -> bool: u, g = r return all(relacionados(g, (x, y)) for x in u for y in u) # 4ª solución # =========== def total4(r: Rel[A]) -> bool: (u, g) = r def aux2(x: A, ys: list[A]) -> bool: if not ys: return True return relacionados(g, (x, ys[0])) and aux2(x, ys[1:]) def aux1(xs: list[A]) -> bool: if not xs: return True return aux2(xs[0], u) and aux1(xs[1:]) return aux1(u) # 5ª solución # =========== def total5(r: Rel[A]) -> bool: (u, g) = r for x in u: for y in u: if not relacionados(g, (x, y)): return False return True # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=0, max_value=10)) def test_total(n: int) -> None: r = relacionArbitraria(n) res = total(r) assert total2(r) == res assert total3(r) == res assert total4(r) == res assert total5(r) == res # La comprobación es # > poetry run pytest -q Relaciones_totales.py # 1 passed in 0.11s |
8. Clausura reflexiva
Usando el tipo de las relaciones binarias, definir la función
clausuraReflexiva :: Eq a => Rel a -> Rel a |
tal que clausuraReflexiva r es la clausura reflexiva de r; es decir, la menor relación reflexiva que contiene a r. Por ejemplo,
λ> clausuraReflexiva (R ([1,3],[(1,1),(3,1)])) R ([1,3],[(1,1),(3,1),(3,3)]) |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
import Relaciones_binarias (Rel(R)) import Data.List (union) import Test.QuickCheck (quickCheck) clausuraReflexiva :: Eq a => Rel a -> Rel a clausuraReflexiva (R (u,g)) = R (u, g `union` [(x,x) | x <- u]) |
from typing import TypeVar from src.Relaciones_binarias import Rel A = TypeVar('A') def clausuraReflexiva(r: Rel[A]) -> Rel[A]: (u, g) = r return (u, list(set(g) | {(x, x) for x in u})) |
9. Clausura simétrica
Usando el tipo de las relaciones binarias, definir la función
clausuraSimetrica :: Eq a => Rel a -> Rel a |
tal que clausuraSimetrica r es la clausura simétrica de r; es decir, la menor relación simétrica que contiene a r. Por ejemplo,
λ> clausuraSimetrica (R ([1,3,5],[(1,1),(3,1),(1,5)])) R ([1,3,5],[(1,1),(3,1),(1,5),(1,3),(5,1)]) |
Comprobar con QuickCheck que clausuraSimetrica es simétrica.
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
import Relaciones_binarias (Rel(R)) import Data.List (union) import Relaciones_simetricas (simetrica) import Test.QuickCheck clausuraSimetrica :: Eq a => Rel a -> Rel a clausuraSimetrica (R (u,g)) = R (u, g `union` [(y,x) | (x,y) <- g]) -- La propiedad es prop_ClausuraSimetrica :: Rel Int -> Bool prop_ClausuraSimetrica r = simetrica (clausuraSimetrica r) -- La función simetrica está definida en el ejercicio -- "Relaciones simétricas" que se encuentra en -- https://bit.ly/3zlO2rH -- La comprobación es -- λ> quickCheck prop_ClausuraSimetrica -- +++ OK, passed 100 tests. |
from typing import TypeVar from hypothesis import given from hypothesis import strategies as st from src.Relaciones_binarias import Rel, relacionArbitraria from src.Relaciones_simetricas import simetrica A = TypeVar('A') def clausuraSimetrica(r: Rel[A]) -> Rel[A]: (u, g) = r return (u, list(set(g) | {(y, x) for (x,y) in g})) # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=0, max_value=10)) def test_irreflexiva(n: int) -> None: r = relacionArbitraria(n) assert simetrica(clausuraSimetrica(r)) # La función simetrica está definida en el ejercicio # "Relaciones simétricas" que se encuentra en # https://bit.ly/3zlO2rH # La comprobación es # > poetry run pytest -q Clausura_simetrica.py # 1 passed in 0.12s |
10. Clausura transitiva
Usando el tipo de las relaciones binarias, definir la función
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,
λ> 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.
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. |
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 |