TAD de los conjuntos: Diferencia simétrica
Utilizando el tipo abstracto de datos de los conjuntos definir la función
1 |
diferenciaSimetrica :: Ord a => Conj a -> Conj a -> Conj a |
tal que diferenciaSimetrica c1 c2
es la diferencia simétrica de los conjuntos c1
y c2
. Por ejemplo,
1 2 3 4 |
λ> ej1 = inserta 5 (inserta 3 (inserta 2 (inserta 7 vacio))) λ> ej2 = inserta 7 (inserta 4 (inserta 3 vacio)) λ> diferenciaSimetrica ej1 ej2 {2, 4, 5} |
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 TAD.Conjunto (Conj, vacio, inserta) import TAD_Diferencia_de_conjuntos (diferencia) import TAD_Interseccion_de_dos_conjuntos (interseccion) import TAD_Union_de_dos_conjuntos (union) import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto) import Test.QuickCheck -- 1ª solución -- =========== diferenciaSimetrica :: Ord a => Conj a -> Conj a -> Conj a diferenciaSimetrica c1 c2 = diferencia (union c1 c2) (interseccion c1 c2) -- 2ª solución -- =========== diferenciaSimetrica2 :: Ord a => Conj a -> Conj a -> Conj a diferenciaSimetrica2 c1 c2 = listaAconjunto ([x | x <- xs, x `notElem` ys] ++ [y | y <- ys, y `notElem` xs]) where xs = conjuntoAlista c1 ys = conjuntoAlista c2 -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_diferenciaSimetrica :: Conj Int -> Conj Int -> Bool prop_diferenciaSimetrica c1 c2 = diferenciaSimetrica c1 c2 == diferenciaSimetrica2 c2 c1 -- La comprobación es -- λ> quickCheck prop_diferenciaSimetrica -- +++ 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 |
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_Diferencia_de_conjuntos import diferencia from src.TAD_Interseccion_de_dos_conjuntos import interseccion 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) # 1ª solución # =========== def diferenciaSimetrica(c1: Conj[A], c2: Conj[A]) -> Conj[A]: return diferencia(union(c1, c2), interseccion(c1, c2)) # 2ª solución # =========== def diferenciaSimetrica2(c1: Conj[A], c2: Conj[A]) -> Conj[A]: xs = conjuntoAlista(c1) ys = conjuntoAlista(c2) return listaAconjunto([x for x in xs if x not in ys] + [y for y in ys if y not in xs]) # 3ª solución # =========== def diferenciaSimetrica3(c1: Conj[A], c2: Conj[A]) -> Conj[A]: r: Conj[A] = vacio() _c1 = deepcopy(c1) _c2 = deepcopy(c2) while not esVacio(_c1): mc1 = menor(_c1) if not pertenece(mc1, c2): r = inserta(mc1, r) _c1 = elimina(mc1, _c1) while not esVacio(_c2): mc2 = menor(_c2) if not pertenece(mc2, c1): r = inserta(mc2, r) _c2 = elimina(mc2, _c2) return r # Comprobación de equivalencia # ============================ # La propiedad es @given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio()) def test_diferenciaSimetrica(c1: Conj[int], c2: Conj[int]) -> None: r = diferenciaSimetrica(c1, c2) assert diferenciaSimetrica2(c1, c2) == r assert diferenciaSimetrica3(c1, c2) == r # La comprobación de las propiedades es # > poetry run pytest -q TAD_Diferencia_simetrica.py # 1 passed in 0.30s |