TAD de las colas: Inclusión de colas
Utilizando el tipo abstracto de datos de las colas, definir la función
|
1 |
contenidaCola :: Eq a => Cola a -> Cola a -> Bool |
tal que contenidaCola c1 c2 se verifica si todos los elementos de la cola c1 son elementos de la cola c2. Por ejemplo,
|
1 2 3 4 5 6 7 |
λ> ej1 = inserta 3 (inserta 2 vacia) λ> ej2 = inserta 3 (inserta 4 vacia) λ> ej3 = inserta 5 (inserta 2 (inserta 3 vacia)) λ> contenidaCola ej1 ej3 True λ> contenidaCola ej2 ej3 False |
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 |
import TAD.Cola (Cola, vacia, inserta, esVacia, primero, resto) import PerteneceCola (perteneceCola) import Transformaciones_colas_listas (colaAlista) import Test.QuickCheck -- 1ª solución -- =========== contenidaCola1 :: Eq a => Cola a -> Cola a -> Bool contenidaCola1 c1 c2 | esVacia c1 = True | otherwise = perteneceCola (primero c1) c2 && contenidaCola1 (resto c1) c2 -- La función perteneceCola está definida en el ejercicio -- "TAD de las colas: Pertenencia a una cola" que se encuentra en -- https://bit.ly/3RcVgqb -- 2ª solución -- =========== contenidaCola2 :: Eq a => Cola a -> Cola a -> Bool contenidaCola2 c1 c2 = contenidaLista (colaAlista c1) (colaAlista c2) -- La función colaAlista está definida en el ejercicio -- "TAD de las colas: Transformaciones entre colas y listas" que se -- encuentra en https://bit.ly/3Xv0oIt contenidaLista :: Eq a => [a] -> [a] -> Bool contenidaLista xs ys = all (`elem` ys) xs -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_contenidaCola :: Cola Int -> Cola Int -> Bool prop_contenidaCola c1 c2 = contenidaCola1 c1 c2 == contenidaCola2 c1 c2 -- La comprobación es -- λ> quickCheck prop_contenidaCola -- +++ 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 |
from copy import deepcopy from typing import TypeVar from hypothesis import given from src.perteneceCola import perteneceCola from src.TAD.cola import (Cola, colaAleatoria, esVacia, inserta, primero, resto, vacia) from src.transformaciones_colas_listas import colaAlista A = TypeVar('A') # 1ª solución # =========== def contenidaCola1(c1: Cola[A], c2: Cola[A]) -> bool: if esVacia(c1): return True return perteneceCola(primero(c1), c2) and contenidaCola1(resto(c1), c2) # L función perteneceCola está definida en el ejercicio # "Pertenencia a una cola" que se encuentra en # https://bit.ly/3RcVgqb # 2ª solución # =========== def contenidaCola2(c1: Cola[A], c2: Cola[A]) -> bool: return set(colaAlista(c1)) <= set(colaAlista(c2)) # La función colaAlista está definida en el ejercicio # "Transformaciones entre colas y listas" que se encuentra en # https://bit.ly/3Xv0oIt # 3ª solución # =========== def contenidaCola3Aux(c1: Cola[A], c2: Cola[A]) -> bool: if c1.esVacia(): return True pc1 = c1.primero() c1.resto() return perteneceCola(pc1, c2) and contenidaCola1(c1, c2) def contenidaCola3(c1: Cola[A], c2: Cola[A]) -> bool: _c1 = deepcopy(c1) return contenidaCola3Aux(_c1, c2) # 4ª solución # =========== def contenidaCola4Aux(c1: Cola[A], c2: Cola[A]) -> bool: while not c1.esVacia(): pc1 = c1.primero() c1.resto() if not perteneceCola(pc1, c2): return False return True def contenidaCola4(c1: Cola[A], c2: Cola[A]) -> bool: _c1 = deepcopy(c1) return contenidaCola4Aux(_c1, c2) # Comprobación de equivalencia de las definiciones # ================================================ # La propiedad es @given(c1=colaAleatoria(), c2=colaAleatoria()) def test_contenidaCola(c1: Cola[int], c2: Cola[int]) -> None: r = contenidaCola1(c1, c2) assert contenidaCola2(c1, c2) == r assert contenidaCola3(c1, c2) == r assert contenidaCola4(c1, c2) == r # La comprobación es # src> poetry run pytest -q contenidaCola.py # 1 passed in 0.44s |