TAD de los conjuntos: Partición según un número
Utilizando el tipo abstracto de datos de los conjuntos definir la función
|
1 |
divide :: (Ord a) => a-> Conj a -> (Conj a, Conj a) |
tal que divide x c es el par formado por dos subconjuntos de c: el de los elementos menores o iguales que x y el de los mayores que x. Por ejemplo,
|
1 2 |
λ> divide 5 (inserta 7 (inserta 2 (inserta 8 vacio))) ({2},{7, 8}) |
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 |
import TAD.Conjunto (Conj, vacio, inserta, esVacio, menor, elimina) import TAD_Particion_por_una_propiedad (particion) import Test.QuickCheck -- 1ª solución -- =========== divide :: Ord a => a-> Conj a -> (Conj a, Conj a) divide x c | esVacio c = (vacio, vacio) | mc <= x = (inserta mc c1, c2) | otherwise = (c1, inserta mc c2) where mc = menor c rc = elimina mc c (c1, c2) = divide x rc -- 2ª solución -- =========== divide2 :: Ord a => a-> Conj a -> (Conj a, Conj a) divide2 x = particion (<= x) -- La función particion está definida en el ejercicio -- "Partición de un conjunto según una propiedad" que se encuentra en -- https://bit.ly/3YCOah5 -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_divide :: Int -> Conj Int -> Bool prop_divide x c = divide x c == divide2 x c -- La comprobación es -- λ> quickCheck prop_divide -- +++ 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 90 91 92 93 94 95 |
from __future__ import annotations from abc import abstractmethod from copy import deepcopy from typing import Protocol, TypeVar from hypothesis import given from hypothesis import strategies as st from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio, inserta, menor, vacio) from src.TAD_Particion_por_una_propiedad import particion class Comparable(Protocol): @abstractmethod def __lt__(self: A, otro: A) -> bool: pass A = TypeVar('A', bound=Comparable) # 1ª solución # =========== def divide(x: A, c: Conj[A]) -> tuple[Conj[A], Conj[A]]: if esVacio(c): return (vacio(), vacio()) mc = menor(c) rc = elimina(mc, c) (c1, c2) = divide(x, rc) if mc <= x: return (inserta(mc, c1), c2) return (c1, inserta(mc, c2)) # 2ª solución # =========== def divide2(x: A, c: Conj[A]) -> tuple[Conj[A], Conj[A]]: return particion(lambda y: y <= x, c) # La función particion está definida en el ejercicio # "Partición de un conjunto según una propiedad" que se encuentra en # https://bit.ly/3YCOah5 # 3ª solución # =========== def divide3Aux(x: A, 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 mc <= x: r = inserta(mc, r) else: s = inserta(mc, s) return (r, s) def divide3(x: A, c: Conj[A]) -> tuple[Conj[A], Conj[A]]: _c = deepcopy(c) return divide3Aux(x, _c) # 4ª solución # =========== def divide4Aux(x: A, 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 mc <= x: r.inserta(mc) else: s.inserta(mc) return (r, s) def divide4(x: A, c: Conj[A]) -> tuple[Conj[A], Conj[A]]: _c = deepcopy(c) return divide4Aux(x, _c) # Comprobación de equivalencia de las definiciones # ================================================ # La propiedad es @given(x=st.integers(), c=conjuntoAleatorio()) def test_particion(x: int, c: Conj[int]) -> None: r = divide(x, c) assert divide2(x, c) == r assert divide3(x, c) == r assert divide4(x, c) == r # La comprobación es # src> poetry run pytest -q TAD_Particion_segun_un_numero.py # 1 passed in 0.30s |