TAD de los conjuntos: Partición de un conjunto según una propiedad
Utilizando el tipo abstracto de datos de los conjuntos definir la función
|
1 |
particion :: Ord a => (a -> Bool) -> Conj a -> (Conj a, Conj a) |
tal que particion c es el par formado por dos conjuntos: el de los elementos de c que verifican p y el de los elementos que no lo verifican. Por ejemplo,
|
1 2 3 |
λ> ej = inserta 5 (inserta 4 (inserta 7 (inserta 2 vacio))) λ> particion even ej ({2, 4},{5, 7}) |
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_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto) import TAD_Subconjunto_por_propiedad (filtra) import Data.List (partition) import Test.QuickCheck.HigherOrder -- 1ª solución -- =========== particion :: Ord a => (a -> Bool) -> Conj a -> (Conj a, Conj a) particion p c = (filtra p c, filtra (not . p) c) -- La función filtra está definida en el ejercicio -- "Subconjunto determinado por una propiedad" que se encuentra en -- https://bit.ly/3lplFoV -- 2ª solución -- =========== particion2 :: Ord a => (a -> Bool) -> Conj a -> (Conj a, Conj a) particion2 p c = (listaAconjunto xs, listaAconjunto ys) where (xs, ys) = partition p (conjuntoAlista c) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_particion :: (Int -> Bool) -> [Int] -> Bool prop_particion p xs = particion p c == particion2 p c where c = listaAconjunto xs -- La comprobación es -- λ> quickCheck' prop_particion -- +++ 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 Callable, Protocol, TypeVar from hypothesis import given from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio, inserta, menor, vacio) from src.TAD_Subconjunto_por_propiedad import filtra class Comparable(Protocol): @abstractmethod def __lt__(self: A, otro: A) -> bool: pass A = TypeVar('A', bound=Comparable) # 1ª solución # =========== def particion(p: Callable[[A], bool], c: Conj[A]) -> tuple[Conj[A], Conj[A]]: return (filtra(p, c), filtra(lambda x: not p(x), c)) # La función filtra está definida en el ejercicio # "Subconjunto determinado por una propiedad" que se encuentra en # https://bit.ly/3lplFoV # 2ª solución # =========== def particion2Aux(p: Callable[[A], bool], c: Conj[A]) -> tuple[Conj[A], Conj[A]]: r: Conj[A] = vacio() s: Conj[A] = vacio() while not esVacio(c): mc = menor(c) c = elimina(mc, c) if p(mc): r = inserta(mc, r) else: s = inserta(mc, s) return (r, s) def particion2(p: Callable[[A], bool], c: Conj[A]) -> tuple[Conj[A], Conj[A]]: _c = deepcopy(c) return particion2Aux(p, _c) # 3ª solución # =========== def particion3Aux(p: Callable[[A], bool], c: Conj[A]) -> tuple[Conj[A], Conj[A]]: r: Conj[A] = Conj() s: Conj[A] = Conj() while not c.esVacio(): mc = c.menor() c.elimina(mc) if p(mc): r.inserta(mc) else: s.inserta(mc) return (r, s) def particion3(p: Callable[[A], bool], c: Conj[A]) -> tuple[Conj[A], Conj[A]]: _c = deepcopy(c) return particion3Aux(p, _c) # Comprobación de equivalencia de las definiciones # ================================================ # La propiedad es @given(c=conjuntoAleatorio()) def test_particion(c: Conj[int]) -> None: r = particion(lambda x: x % 2 == 0, c) assert particion2(lambda x: x % 2 == 0, c) == r assert particion3(lambda x: x % 2 == 0, c) == r # La comprobación es # src> poetry run pytest -q TAD_Particion_por_una_propiedad.py # 1 passed in 0.28s |