TAD de los conjuntos: Diferencia de conjuntos
Utilizando el tipo abstracto de datos de los conjuntos definir la función
1 |
diferencia :: Ord a => Conj a -> Conj a -> Conj a |
tal que diferencia c1 c2
es el conjunto de los elementos de c1
que no son elementos de c2
. Por ejemplo,
1 2 3 4 5 6 7 8 |
λ> ej1 = inserta 5 (inserta 3 (inserta 2 (inserta 7 vacio))) λ> ej2 = inserta 7 (inserta 4 (inserta 3 vacio)) λ> diferencia ej1 ej2 {2, 5} λ> diferencia ej2 ej1 {4} λ> diferencia ej1 ej1 {} |
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 |
import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, pertenece, esVacio) import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto) import Test.QuickCheck -- 1ª solución -- =========== diferencia :: Ord a => Conj a -> Conj a -> Conj a diferencia c1 c2 | esVacio c1 = vacio | pertenece mc1 c2 = diferencia rc1 c2 | otherwise = inserta mc1 (diferencia rc1 c2) where mc1 = menor c1 rc1 = elimina mc1 c1 -- 2ª solución -- =========== diferencia2 :: Ord a => Conj a -> Conj a -> Conj a diferencia2 c1 c2 = listaAconjunto [x | x <- conjuntoAlista c1, not (pertenece x c2)] -- Las funciones conjuntoAlista y listaAconjunto 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_diferencia :: Conj Int -> Conj Int -> Bool prop_diferencia c1 c2 = diferencia c1 c2 == diferencia2 c1 c2 -- La comprobación es -- λ> quickCheck prop_diferencia -- +++ 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 |
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_Transformaciones_conjuntos_listas import (conjuntoAlista, listaAconjunto) class Comparable(Protocol): @abstractmethod def __lt__(self: A, otro: A) -> bool: pass A = TypeVar('A', bound=Comparable) # 1ª solución # =========== def diferencia(c1: Conj[A], c2: Conj[A]) -> Conj[A]: if esVacio(c1): return vacio() mc1 = menor(c1) rc1 = elimina(mc1, c1) if pertenece(mc1, c2): return diferencia(rc1, c2) return inserta(mc1, diferencia(rc1, c2)) # 2ª solución # =========== def diferencia2(c1: Conj[A], c2: Conj[A]) -> Conj[A]: return listaAconjunto([x for x in conjuntoAlista(c1) if not pertenece(x, c2)]) # Las funciones conjuntoAlista y listaAconjunto está definida en el # ejercicio Transformaciones entre conjuntos y listas" que se encuentra # en https://bit.ly/3RexzxH # 3ª solución # =========== def diferencia3Aux(c1: Conj[A], c2: Conj[A]) -> Conj[A]: r: Conj[A] = vacio() while not esVacio(c1): mc1 = menor(c1) if not pertenece(mc1, c2): r = inserta(mc1, r) c1 = elimina(mc1, c1) return r def diferencia3(c1: Conj[A], c2: Conj[A]) -> Conj[A]: _c1 = deepcopy(c1) return diferencia3Aux(_c1, c2) # 4ª solución # =========== def diferencia4Aux(c1: Conj[A], c2: Conj[A]) -> Conj[A]: r: Conj[A] = Conj() while not c1.esVacio(): mc1 = c1.menor() if not c2.pertenece(mc1): r.inserta(mc1) c1.elimina(mc1) return r def diferencia4(c1: Conj[A], c2: Conj[A]) -> Conj[A]: _c1 = deepcopy(c1) return diferencia4Aux(_c1, c2) # Comprobación de equivalencia # ============================ # La propiedad es @given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio()) def test_diferencia(c1: Conj[int], c2: Conj[int]) -> None: r = diferencia(c1, c2) assert diferencia2(c1, c2) == r assert diferencia3(c1, c2) == r assert diferencia4(c1, c2) == r # La comprobación de las propiedades es # > poetry run pytest -q TAD_Diferencia_de_conjuntos.py # 1 passed in 0.31s |