La semana en Exercitium (1 de abril de 2023)
Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. TAD de los conjuntos: Producto cartesiano de dos conjuntos
- 2. Relaciones binarias
- 3. Universo y grafo de una relación binaria
- 4. Relaciones reflexivas
- 5. Relaciones simétricas
A continuación se muestran las soluciones.
1. TAD de los conjuntos: Producto cartesiano de dos conjuntos
Utilizando el tipo abstracto de datos de los conjuntos (https://bit.ly/3HbB7fo) definir la función
1 |
productoC :: (Ord a, Ord b) => Conj a -> Conj b -> Conj (a,b) |
tal que productoC c1 c2
es el producto cartesiano de los conjuntos c1
y c2
. Por ejemplo,
1 2 3 4 |
λ> ej1 = inserta 2 (inserta 5 vacio) λ> ej2 = inserta 9 (inserta 4 (inserta 3 vacio)) λ> productoC ej1 ej2 {(2,3), (2,4), (2,9), (5,3), (5,4), (5,9)} |
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 |
import TAD.Conjunto (Conj, vacio, inserta, esVacio, menor, elimina) import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto) import TAD_Union_de_dos_conjuntos (union) import Test.QuickCheck -- 1ª solución -- =========== productoC :: (Ord a, Ord b) => Conj a -> Conj b -> Conj (a,b) productoC c1 c2 | esVacio c1 = vacio | otherwise = agrega mc1 c2 `union` productoC rc1 c2 where mc1 = menor c1 rc1 = elimina mc1 c1 -- (agrega x c) es el conjunto de los pares de x con los elementos de -- c. Por ejemplo, -- λ> agrega 2 (inserta 9 (inserta 4 (inserta 3 vacio))) -- {(2,3), (2,4), (2,9)} agrega :: (Ord a, Ord b) => a -> Conj b -> Conj (a,b) agrega x c | esVacio c = vacio | otherwise = inserta (x, mc) (agrega x rc) where mc = menor c rc = elimina mc c -- La función union está definida en el ejercicio -- "Unión de dos conjuntos" que se encuentra en -- https://bit.ly/3Y1jBl8 -- 2ª solución -- =========== productoC2 :: (Ord a, Ord b) => Conj a -> Conj b -> Conj (a,b) productoC2 c1 c2 = foldr inserta vacio [(x,y) | x <- xs, y <- ys] where xs = conjuntoAlista c1 ys = conjuntoAlista c2 -- 3ª solución -- =========== productoC3 :: (Ord a, Ord b) => Conj a -> Conj b -> Conj (a,b) productoC3 c1 c2 = listaAconjunto [(x,y) | x <- xs, y <- ys] where xs = conjuntoAlista c1 ys = conjuntoAlista c2 -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_productoC :: Conj Int -> Conj Int -> Bool prop_productoC c1 c2 = all (== productoC c1 c2) [productoC2 c1 c2, productoC3 c1 c2] -- La comprobación es -- λ> quickCheck prop_productoC -- +++ 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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
from __future__ import annotations from abc import abstractmethod from copy import deepcopy from functools import reduce from typing import Protocol, TypeVar from hypothesis import given from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio, inserta, menor, vacio) from src.TAD_Transformaciones_conjuntos_listas import (conjuntoAlista, listaAconjunto) from src.TAD_Union_de_dos_conjuntos import union class Comparable(Protocol): @abstractmethod def __lt__(self: A, otro: A) -> bool: pass A = TypeVar('A', bound=Comparable) B = TypeVar('B', bound=Comparable) # 1ª solución # =========== # (agrega x c) es el conjunto de los pares de x con los elementos de # c. Por ejemplo, # >>> agrega(2, inserta(9, inserta(4, inserta(3, vacio())))) # {(2, 3), (2, 4), (2, 9)} def agrega(x: A, c: Conj[B]) -> Conj[tuple[A, B]]: if esVacio(c): return vacio() mc = menor(c) rc = elimina(mc, c) return inserta((x, mc), agrega(x, rc)) def productoC(c1: Conj[A], c2: Conj[B]) -> Conj[tuple[A, B]]: if esVacio(c1): return vacio() mc1 = menor(c1) rc1 = elimina(mc1, c1) return union(agrega(mc1, c2), productoC(rc1, c2)) # La función union está definida en el ejercicio # "Unión de dos conjuntos" que se encuentra en # https://bit.ly/3Y1jBl8 # 2ª solución # =========== def productoC2(c1: Conj[A], c2: Conj[B]) -> Conj[tuple[A, B]]: xs = conjuntoAlista(c1) ys = conjuntoAlista(c2) return reduce(lambda bs, a: inserta(a, bs), [(x,y) for x in xs for y in ys], vacio()) # 3ª solución # =========== def productoC3(c1: Conj[A], c2: Conj[B]) -> Conj[tuple[A, B]]: xs = conjuntoAlista(c1) ys = conjuntoAlista(c2) return listaAconjunto([(x,y) for x in xs for y in ys]) # 4ª solución # =========== def agrega4Aux(x: A, c: Conj[B]) -> Conj[tuple[A, B]]: r: Conj[tuple[A, B]] = vacio() while not esVacio(c): mc = menor(c) c = elimina(mc, c) r = inserta((x, mc), r) return r def agrega4(x: A, c: Conj[B]) -> Conj[tuple[A, B]]: _c = deepcopy(c) return agrega4Aux(x, _c) def productoC4(c1: Conj[A], c2: Conj[B]) -> Conj[tuple[A, B]]: r: Conj[tuple[A, B]] = vacio() while not esVacio(c1): mc1 = menor(c1) c1 = elimina(mc1, c1) r = union(agrega4(mc1, c2), r) return r # 5ª solución # =========== def agrega5Aux(x: A, c: Conj[B]) -> Conj[tuple[A, B]]: r: Conj[tuple[A, B]] = Conj() while not c.esVacio(): mc = c.menor() c.elimina(mc) r.inserta((x, mc)) return r def agrega5(x: A, c: Conj[B]) -> Conj[tuple[A, B]]: _c = deepcopy(c) return agrega5Aux(x, _c) def productoC5(c1: Conj[A], c2: Conj[B]) -> Conj[tuple[A, B]]: r: Conj[tuple[A, B]] = Conj() while not c1.esVacio(): mc1 = c1.menor() c1.elimina(mc1) r = union(agrega5(mc1, c2), r) return r # Comprobación de equivalencia # ============================ # La propiedad es @given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio()) def test_productoC(c1: Conj[int], c2: Conj[int]) -> None: r = productoC(c1, c2) assert productoC2(c1, c2) == r assert productoC3(c1, c2) == r assert productoC4(c1, c2) == r # La comprobación de las propiedades es # > poetry run pytest -q TAD_Producto_cartesiano.py # 1 passed in 0.35s |
2. Relaciones binarias
Una relación 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 binarias sobre a, y la función
1 |
esRelacionBinaria :: Eq a => Rel a -> Bool |
tal que esRelacionBinaria r
se verifica si r
es una relación binaria. Por ejemplo,
1 2 3 4 |
λ> esRelacionBinaria (R ([1, 3], [(3, 1), (3, 3)])) True λ> esRelacionBinaria (R ([1, 3], [(3, 1), (3, 2)])) False |
Además, definir un generador de relaciones binarias y comprobar que las relaciones que genera son relaciones binarias.
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 |
import Data.List (nub) import Test.QuickCheck newtype Rel a = R ([a], [(a,a)]) deriving (Eq, Show) -- 1ª solución -- =========== esRelacionBinaria :: Eq a => Rel a -> Bool esRelacionBinaria (R (u, g)) = and [x `elem` u && y `elem` u | (x,y) <- g] -- 2ª solución -- =========== esRelacionBinaria2 :: Eq a => Rel a -> Bool esRelacionBinaria2 (R (u, g)) = all (\(x,y) -> x `elem` u && y `elem` u) g -- 3ª solución -- =========== esRelacionBinaria3 :: Eq a => Rel a -> Bool esRelacionBinaria3 (R (_, [])) = True esRelacionBinaria3 (R (u, (x,y):g)) = x `elem` u && y `elem` u && esRelacionBinaria3 (R (u, g)) -- Comprobación de equivalencia -- ============================ -- Generador de relaciones binarias. Por ejemplo, -- λ> sample (relacionArbitraria :: Gen (Rel Int)) -- R ([0],[]) -- R ([0,-1,1],[(0,-1),(0,1),(-1,1),(1,0)]) -- R ([1],[]) -- R ([-5,3],[(-5,-5),(-5,3),(3,-5),(3,3)]) -- R ([-2,-7],[(-7,-7)]) -- R ([11,-7],[]) -- R ([0],[]) -- R ([-13,-11],[(-13,-13)]) relacionArbitraria :: (Arbitrary a, Eq a) => Gen (Rel a) relacionArbitraria = do n <- choose (0, 10) u1 <- vectorOf n arbitrary let u = nub u1 g <- sublistOf [(x,y) | x <- u, y <- u] return (R (u, g)) -- Relaciones es una subclase de Arbitrary. instance (Arbitrary a, Eq a) => Arbitrary (Rel a) where arbitrary = relacionArbitraria -- La propiedad es prop_esRelacionBinaria :: Rel Int -> Bool prop_esRelacionBinaria r = esRelacionBinaria r && esRelacionBinaria2 r && esRelacionBinaria3 r -- La comprobación es -- λ> quickCheck prop_esRelacionBinaria -- +++ 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 89 90 91 92 93 94 95 96 97 98 99 100 |
from random import choice, randint, sample from typing import TypeVar from hypothesis import given from hypothesis import strategies as st A = TypeVar('A') Rel = tuple[list[A], list[tuple[A, A]]] # 1ª solución # =========== def esRelacionBinaria(r: Rel[A]) -> bool: (u, g) = r return all((x in u and y in u for (x, y) in g)) # 2ª solución # =========== def esRelacionBinaria2(r: Rel[A]) -> bool: (u, g) = r if not g: return True (x, y) = g[0] return x in u and y in u and esRelacionBinaria2((u, g[1:])) # 3ª solución # =========== def esRelacionBinaria3(r: Rel[A]) -> bool: (u, g) = r for (x, y) in g: if x not in u or y not in u: return False return True # Generador de relaciones binarias # ================================ # conjuntoArbitrario(n) es un conjunto arbitrario cuyos elementos están # entre 0 y n-1. Por ejemplo, # >>> conjuntoArbitrario(10) # [8, 9, 4, 5] # >>> conjuntoArbitrario(10) # [1, 2, 3, 4, 5, 6, 7, 8, 9] # >>> conjuntoArbitrario(10) # [0, 1, 2, 3, 6, 7, 9] # >>> conjuntoArbitrario(10) # [8, 2, 3, 7] def conjuntoArbitrario(n: int) -> list[int]: xs = sample(range(n), randint(0, n)) return list(set(xs)) # productoCartesiano(xs, ys) es el producto cartesiano de xs e ys. Por # ejemplo, # >>> productoCartesiano([2, 3], [1, 7, 5]) # [(2, 1), (2, 7), (2, 5), (3, 1), (3, 7), (3, 5)] def productoCartesiano(xs: list[int], ys: list[int]) -> list[tuple[int, int]]: return [(x, y) for x in xs for y in ys] # sublistaArbitraria(xs) es una sublista arbitraria de xs. Por ejemplo, # >>> sublistaArbitraria(range(10)) # [3, 7] # >>> sublistaArbitraria(range(10)) # [] # >>> sublistaArbitraria(range(10)) # [4, 1, 0, 9, 8, 7, 5, 6, 2, 3] def sublistaArbitraria(xs: list[A]) -> list[A]: n = len(xs) k = randint(0, n) return sample(xs, k) # relacionArbitraria(n) es una relación arbitraria tal que los elementos # de su universo están entre 0 y n-1. Por ejemplo, # >>> relacionArbitraria(3) # ([0, 1], [(1, 0), (1, 1)]) # >>> relacionArbitraria(3) # ([], []) # >>> relacionArbitraria(5) # ([0, 2, 3, 4], [(2, 0), (3, 3), (2, 3), (4, 0), (3, 4), (4, 2)]) def relacionArbitraria(n: int) -> Rel[int]: u = conjuntoArbitrario(n) g = sublistaArbitraria(productoCartesiano(u, u)) return (u, g) # Comprobación de la propiedad # ============================ # La propiedad es @given(st.integers(min_value=0, max_value=10)) def test_esRelacionBinaria(n: int) -> None: r = relacionArbitraria(n) assert esRelacionBinaria(r) assert esRelacionBinaria2(r) assert esRelacionBinaria3(r) # La comprobación es # > poetry run pytest -q Relaciones_binarias.py # 1 passed in 0.14s |
3. Universo y grafo de una relación binaria
Usando el tipo de las relaciones binarias, definir las funciones
1 2 |
universo :: Eq a => Rel a -> [a] grafo :: Eq a => ([a],[(a,a)]) -> [(a,a)] |
tales que
universo r
es el universo de la relaciónr
. Por ejemplo,
1 2 3 |
λ> r = R ([1, 3],[(3, 1), (3, 3)]) λ> universo r [1,3] |
grafo r
es el grafo de la relación r. Por ejemplo,
1 2 |
λ> grafo r [(3,1),(3,3)] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 |
import Relaciones_binarias universo :: Eq a => Rel a -> [a] universo (R (u,_)) = u grafo :: Eq a => Rel a -> [(a,a)] grafo (R (_,g)) = g |
1 2 3 4 5 6 7 8 9 10 11 |
from typing import TypeVar A = TypeVar('A') Rel = tuple[list[A], list[tuple[A, A]]] def universo(r: Rel[A]) -> list[A]: return r[0] def grafo(r: Rel[A]) -> list[tuple[A, A]]: return r[1] |
4. Relaciones reflexivas
Usando el tipo de las relaciones binarias, definir la función
1 |
reflexiva :: Eq a => Rel a -> Bool |
tal que reflexiva r
se verifica si la relación r
es reflexiva. Por ejemplo,
1 2 |
reflexiva (R ([1,3],[(1,1),(1,3),(3,3)])) == True reflexiva (R ([1,2,3],[(1,1),(1,3),(3,3)])) == 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 |
module Relaciones_reflexivas where import Relaciones_binarias (Rel(R)) import Test.QuickCheck -- 1ª solución -- =========== reflexiva :: Eq a => Rel a -> Bool reflexiva (R ([], _)) = True reflexiva (R (x:xs, ps)) = (x, x) `elem` ps && reflexiva (R (xs, ps)) -- 2ª solución -- =========== reflexiva2 :: Eq a => Rel a -> Bool reflexiva2 (R (us,ps)) = and [(x,x) `elem` ps | x <- us] -- 3ª solución -- =========== reflexiva3 :: Eq a => Rel a -> Bool reflexiva3 (R (us,ps)) = all (`elem` ps) [(x,x) | x <- us] -- 4ª solución -- =========== reflexiva4 :: Eq a => Rel a -> Bool reflexiva4 (R (us,ps)) = all (\x -> (x,x) `elem` ps) us -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_reflexiva :: Rel Int -> Bool prop_reflexiva r = all (== reflexiva r) [reflexiva2 r, reflexiva3 r, reflexiva4 r] -- La comprobación es -- λ> quickCheck prop_reflexiva -- +++ 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 |
from random import choice, randint, sample 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 reflexiva(r: Rel[A]) -> bool: (us, ps) = r if not us: return True return (us[0], us[0]) in ps and reflexiva((us[1:], ps)) # 2ª solución # =========== def reflexiva2(r: Rel[A]) -> bool: (us, ps) = r return all(((x,x) in ps for x in us)) # 3ª solución # =========== def reflexiva3(r: Rel[A]) -> bool: (us, ps) = r for x in us: if (x, x) not in ps: return False return True # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=0, max_value=10)) def test_reflexiva(n: int) -> None: r = relacionArbitraria(n) res = reflexiva(r) assert reflexiva2(r) == res assert reflexiva3(r) == res # La comprobación es # > poetry run pytest -q Relaciones_reflexivas.py # 1 passed in 0.41s |
5. Relaciones simétricas
Usando el tipo de las relaciones binarias, definir la función
1 |
simetrica :: Eq a => Rel a -> Bool |
tal que simetrica r
se verifica si la relación r
es simétrica. Por ejemplo,
1 2 3 |
simetrica (R ([1,3],[(1,1),(1,3),(3,1)])) == True simetrica (R ([1,3],[(1,1),(1,3),(3,2)])) == False simetrica (R ([1,3],[])) == True |
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 |
import Relaciones_binarias (Rel(R)) import Test.QuickCheck -- 1ª solución -- =========== simetrica :: Eq a => Rel a -> Bool simetrica (R (_,g)) = and [(y,x) `elem` g | (x,y) <- g] -- 2ª solución -- =========== simetrica2 :: Eq a => Rel a -> Bool simetrica2 (R (_,g)) = all (\(x,y) -> (y,x) `elem` g) g -- 3ª solución -- =========== simetrica3 :: Eq a => Rel a -> Bool simetrica3 (R (_,g)) = aux g where aux [] = True aux ((x,y):ps) = (y,x) `elem` g && aux ps -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_simetrica :: Rel Int -> Bool prop_simetrica r = all (== simetrica r) [simetrica2 r, simetrica3 r] -- La comprobación es -- λ> quickCheck prop_simetrica -- +++ 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 |
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 simetrica(r: Rel[A]) -> bool: (_, g) = r return all(((y, x) in g for (x, y) in g)) # 2ª solución # =========== def simetrica2(r: Rel[A]) -> bool: (_, g) = r def aux(ps: list[tuple[A, A]]) -> bool: if not ps: return True (x, y) = ps[0] return (y, x) in g and aux(ps[1:]) return aux(g) # 3ª solución # =========== def simetrica3(r: Rel[A]) -> bool: (_, g) = r for (x, y) in g: if (y, x) not in g: 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 = simetrica(r) assert simetrica2(r) == res assert simetrica3(r) == res # La comprobación es # > poetry run pytest -q Relaciones_simetricas.py # 1 passed in 0.11s |