TAD de los conjuntos: Intersección de varios conjuntos
Utilizando el tipo abstracto de datos de los conjuntos definir la función
|
1 |
interseccionG :: Ord a => [Conj a] -> Conj a |
tal que interseccionG cs es la intersección de la lista de conjuntos cs. Por ejemplo,
|
1 2 3 4 5 |
λ> ej1 = inserta 2 (inserta 3 (inserta 5 vacio)) λ> ej2 = inserta 5 (inserta 2 (inserta 7 vacio)) λ> ej3 = inserta 3 (inserta 2 (inserta 5 vacio)) λ> interseccionG [ej1, ej2, ej3] {2, 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 |
import TAD.Conjunto (Conj, vacio, inserta) import TAD_Interseccion_de_dos_conjuntos (interseccion) import Test.QuickCheck -- 1ª solución -- =========== interseccionG :: Ord a => [Conj a] -> Conj a interseccionG [c] = c interseccionG (cs:css) = interseccion cs (interseccionG css) -- 2ª solución -- =========== interseccionG2 :: Ord a => [Conj a] -> Conj a interseccionG2 = foldr1 interseccion -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_interseccionG :: NonEmptyList (Conj Int) -> Bool prop_interseccionG (NonEmpty cs) = interseccionG cs == interseccionG2 cs -- La comprobación es -- λ> quickCheck prop_interseccionG1 -- +++ 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 |
from __future__ import annotations from abc import abstractmethod from functools import reduce from typing import Protocol, TypeVar from hypothesis import given from hypothesis import strategies as st from src.TAD.conjunto import Conj, conjuntoAleatorio, inserta, vacio from src.TAD_Interseccion_de_dos_conjuntos import interseccion class Comparable(Protocol): @abstractmethod def __lt__(self: A, otro: A) -> bool: pass A = TypeVar('A', bound=Comparable) # 1ª solución # =========== def interseccionG(cs: list[Conj[A]]) -> Conj[A]: if len(cs) == 1: return cs[0] return interseccion(cs[0], interseccionG(cs[1:])) # 2ª solución # =========== def interseccionG2(cs: list[Conj[A]]) -> Conj[A]: return reduce(interseccion, cs[1:], cs[0]) # 3ª solución # =========== def interseccionG3(cs: list[Conj[A]]) -> Conj[A]: r = cs[0] for c in cs[1:]: r = interseccion(c, r) return r # Comprobación de equivalencia # ============================ # La propiedad es @given(st.lists(conjuntoAleatorio(), min_size=1, max_size=10)) def test_interseccionG(cs: list[Conj[int]]) -> None: r = interseccionG(cs) assert interseccionG2(cs) == r assert interseccionG3(cs) == r # La comprobación de las propiedades es # > poetry run pytest -q TAD_Interseccion_de_varios_conjuntos.py # 1 passed in 0.60s |