TAD de los conjuntos: Conjuntos disjuntos
Utilizando el tipo abstracto de datos de los conjuntos definir la función
|
1 |
disjuntos :: Ord a => Conj a -> Conj a -> Bool |
tal que disjuntos c1 c2 se verifica si los conjuntos c1 y c2 son disjuntos. Por ejemplo,
|
1 2 3 4 5 6 7 |
λ> ej1 = inserta 2 (inserta 5 vacio) λ> ej2 = inserta 4 (inserta 3 vacio) λ> ej3 = inserta 5 (inserta 3 vacio) λ> disjuntos ej1 ej2 True λ> disjuntos ej1 ej3 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 |
import TAD.Conjunto (Conj, vacio, inserta, esVacio, menor, elimina, pertenece) import TAD_Interseccion_de_dos_conjuntos (interseccion) import TAD_Transformaciones_conjuntos_listas (conjuntoAlista) import Test.QuickCheck -- 1ª solución -- =========== disjuntos :: Ord a => Conj a -> Conj a -> Bool disjuntos c1 c2 = esVacio (interseccion c1 c2) -- La función interseccion está definida en el ejercicio -- "Intersección de dos conjuntos" que se encuentra en -- https://bit.ly/3jDL9xZ -- 2ª solución -- =========== disjuntos2 :: Ord a => Conj a -> Conj a -> Bool disjuntos2 c1 c2 | esVacio c1 = True | pertenece mc1 c2 = False | otherwise = disjuntos2 rc1 c2 where mc1 = menor c1 rc1 = elimina mc1 c1 -- 3ª solución -- =========== disjuntos3 :: Ord a => Conj a -> Conj a -> Bool disjuntos3 c1 c2 = all (`notElem` ys) xs where xs = conjuntoAlista c1 ys = conjuntoAlista c2 -- La función conjuntoAlista está definida en el ejercicio -- "Transformaciones entre conjuntos y listas" que se encuentra en -- https://bit.ly/3RexzxH -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_disjuntos :: Conj Int -> Conj Int -> Bool prop_disjuntos c1 c2 = all (== disjuntos c1 c2) [disjuntos2 c1 c2, disjuntos3 c1 c2] -- La comprobación es -- λ> quickCheck prop_disjuntos -- +++ 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 |
from __future__ import annotations from abc import abstractmethod from copy import deepcopy from typing import Protocol, TypeVar from hypothesis import given from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio, inserta, menor, pertenece, vacio) from src.TAD_Interseccion_de_dos_conjuntos import interseccion from src.TAD_Transformaciones_conjuntos_listas import conjuntoAlista class Comparable(Protocol): @abstractmethod def __lt__(self: A, otro: A) -> bool: pass A = TypeVar('A', bound=Comparable) # 1ª solución # =========== def disjuntos(c1: Conj[A], c2: Conj[A]) -> bool: return esVacio(interseccion(c1, c2)) # 2ª solución # =========== def disjuntos2(c1: Conj[A], c2: Conj[A]) -> bool: if esVacio(c1): return True mc1 = menor(c1) rc1 = elimina(mc1, c1) if pertenece(mc1, c2): return False return disjuntos2(rc1, c2) # 3ª solución # =========== def disjuntos3(c1: Conj[A], c2: Conj[A]) -> bool: xs = conjuntoAlista(c1) ys = conjuntoAlista(c2) return all((x not in ys for x in xs)) # La función conjuntoAlista está definida en el ejercicio # "Transformaciones entre conjuntos y listas" que se encuentra en # https://bit.ly/3RexzxH # 4ª solución # =========== def disjuntos4Aux(c1: Conj[A], c2: Conj[A]) -> bool: while not esVacio(c1): mc1 = menor(c1) if pertenece(mc1, c2): return False c1 = elimina(mc1, c1) return True def disjuntos4(c1: Conj[A], c2: Conj[A]) -> bool: _c1 = deepcopy(c1) return disjuntos4Aux(_c1, c2) # 5ª solución # =========== def disjuntos5Aux(c1: Conj[A], c2: Conj[A]) -> bool: while not c1.esVacio(): mc1 = c1.menor() if c2.pertenece(mc1): return False c1.elimina(mc1) return True def disjuntos5(c1: Conj[A], c2: Conj[A]) -> bool: _c1 = deepcopy(c1) return disjuntos5Aux(_c1, c2) # Comprobación de equivalencia # ============================ # La propiedad es @given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio()) def test_disjuntos(c1: Conj[int], c2: Conj[int]) -> None: r = disjuntos(c1, c2) assert disjuntos2(c1, c2) == r assert disjuntos3(c1, c2) == r assert disjuntos4(c1, c2) == r assert disjuntos5(c1, c2) == r # La comprobación de las propiedades es # > poetry run pytest -q TAD_Conjuntos_disjuntos.py # 1 passed in 0.34s |