TAD de los conjuntos: Intersección de dos conjuntos
Utilizando el tipo abstracto de datos de los conjuntos definir la función
1 |
interseccion :: Ord a => Conj a -> Conj a -> Conj a |
tal que interseccion c1 c2
es la intersección de los conjuntos c1
y c2
. Por ejemplo,
1 2 3 4 |
λ> ej1 = inserta 3 (inserta 5 (inserta 2 vacio)) λ> ej2 = inserta 2 (inserta 4 (inserta 3 vacio)) λ> interseccion ej1 ej2 {2, 3} |
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 |
import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, pertenece, esVacio) import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto) import Data.List (intersect) import Test.QuickCheck -- 1ª solución -- =========== interseccion :: Ord a => Conj a -> Conj a -> Conj a interseccion c1 c2 | esVacio c1 = vacio | pertenece mc1 c2 = inserta mc1 (interseccion rc1 c2) | otherwise = interseccion rc1 c2 where mc1 = menor c1 rc1 = elimina mc1 c1 -- 2ª solución -- =========== interseccion2 :: Ord a => Conj a -> Conj a -> Conj a interseccion2 c1 c2 = listaAconjunto [x | x <- conjuntoAlista c1, x `pertenece` 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 -- =========== interseccion3 :: Ord a => Conj a -> Conj a -> Conj a interseccion3 c1 c2 = listaAconjunto (conjuntoAlista c1 `intersect` conjuntoAlista c2) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_interseccion :: Conj Int -> Conj Int -> Bool prop_interseccion c1 c2 = all (== interseccion c1 c2) [interseccion2 c1 c2, interseccion3 c1 c2] -- La comprobación es -- λ> quickCheck prop_interseccion -- +++ 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 |
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 interseccion(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 inserta(mc1, interseccion(rc1, c2)) return interseccion(rc1, c2) # 2ª solución # =========== def interseccion2(c1: Conj[A], c2: Conj[A]) -> Conj[A]: return listaAconjunto([x for x in conjuntoAlista(c1) if 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 interseccion3(c1: Conj[A], c2: Conj[A]) -> Conj[A]: r: Conj[A] = vacio() while not esVacio(c1): mc1 = menor(c1) c1 = elimina(mc1, c1) if pertenece(mc1, c2): r = inserta(mc1, r) return r # 4ª solución # =========== def interseccion4Aux(c1: Conj[A], c2: Conj[A]) -> Conj[A]: r: Conj[A] = vacio() while not c1.esVacio(): mc1 = c1.menor() c1.elimina(mc1) if c2.pertenece(mc1): r.inserta(mc1) return r def interseccion4(c1: Conj[A], c2: Conj[A]) -> Conj[A]: _c1 = deepcopy(c1) return interseccion4Aux(_c1, c2) # Comprobación de equivalencia # ============================ # La propiedad es @given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio()) def test_interseccion(c1: Conj[int], c2: Conj[int]) -> None: r = interseccion(c1, c2) assert interseccion2(c1, c2) == r assert interseccion3(c1, c2) == r assert interseccion4(c1, c2) == r # La comprobación de las propiedades es # > poetry run pytest -q TAD_Interseccion_de_dos_conjuntos.py # 1 passed in 0.30s |