TAD de las pilas: Inclusión de pilas
Utilizando el tipo abstracto de datos de las pilas, definir la función
|
1 |
contenidaPila :: Eq a => Pila a -> Pila a -> Bool |
tal que contenidaPila p1 p2 se verifica si todos los elementos de de la pila p1 son elementos de la pila p2. Por ejemplo,
|
1 2 3 4 5 6 7 |
λ> ej1 = apila 3 (apila 2 vacia) λ> ej2 = apila 3 (apila 4 vacia) λ> ej3 = apila 5 (apila 2 (apila 3 vacia)) λ> contenidaPila ej1 ej3 True λ> contenidaPila 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 45 46 47 48 49 50 51 |
import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila) import PertenecePila (pertenecePila) import Test.QuickCheck -- 1ª solución -- =========== -- Se usará la función pertenecePila del ejercicio -- "Pertenencia a una pila" que se encuentra en -- https://bit.ly/3WdM9GC contenidaPila1 :: Eq a => Pila a -> Pila a -> Bool contenidaPila1 p1 p2 | esVacia p1 = True | otherwise = pertenecePila cp1 p2 && contenidaPila1 dp1 p2 where cp1 = cima p1 dp1 = desapila p1 -- 2ª solución -- =========== contenidaPila2 :: Eq a => Pila a -> Pila a -> Bool contenidaPila2 p1 p2 = contenidaLista (pilaAlista p1) (pilaAlista p2) contenidaLista :: Eq a => [a] -> [a] -> Bool contenidaLista xs ys = all (`elem` ys) xs -- (pilaALista p) es la lista formada por los elementos de la -- lista p. Por ejemplo, -- λ> pilaAlista (apila 5 (apila 2 (apila 3 vacia))) -- [3, 2, 5] pilaAlista :: Pila a -> [a] pilaAlista = reverse . aux where aux p | esVacia p = [] | otherwise = cp : aux dp where cp = cima p dp = desapila p -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_contenidaPila :: Pila Int -> Pila Int -> Bool prop_contenidaPila p1 p2 = contenidaPila1 p1 p2 == contenidaPila2 p1 p2 -- La comprobación es -- λ> quickCheck prop_contenidaPila -- +++ 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 |
from copy import deepcopy from typing import TypeVar from hypothesis import given from src.pertenecePila import pertenecePila from src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria, vacia) from src.transformaciones_pilas_listas import pilaAlista A = TypeVar('A') # 1ª solución # =========== # Se usará la función pertenecePila del ejercicio # "Pertenencia a una pila" que se encuentra en # https://bit.ly/3WdM9GC def contenidaPila1(p1: Pila[A], p2: Pila[A]) -> bool: if esVacia(p1): return True cp1 = cima(p1) dp1 = desapila(p1) return pertenecePila(cp1, p2) and contenidaPila1(dp1, p2) # 2ª solución # =========== # Se usará la función pilaAlista del ejercicio # "Transformaciones entre pilas y listas" que se encuentra en # https://bit.ly/3ZHewQ8 def contenidaPila2(p1: Pila[A], p2: Pila[A]) -> bool: return set(pilaAlista(p1)) <= set(pilaAlista(p2)) # 3ª solución # =========== def contenidaPila3Aux(p1: Pila[A], p2: Pila[A]) -> bool: if p1.esVacia(): return True cp1 = p1.cima() p1.desapila() return pertenecePila(cp1, p2) and contenidaPila1(p1, p2) def contenidaPila3(p1: Pila[A], p2: Pila[A]) -> bool: q = deepcopy(p1) return contenidaPila3Aux(q, p2) # 4ª solución # =========== def contenidaPila4Aux(p1: Pila[A], p2: Pila[A]) -> bool: while not p1.esVacia(): cp1 = p1.cima() p1.desapila() if not pertenecePila(cp1, p2): return False return True def contenidaPila4(p1: Pila[A], p2: Pila[A]) -> bool: q = deepcopy(p1) return contenidaPila4Aux(q, p2) # Comprobación de equivalencia de las definiciones # ================================================ # La propiedad es @given(p1=pilaAleatoria(), p2=pilaAleatoria()) def test_contenidaPila(p1: Pila[int], p2: Pila[int]) -> None: r = contenidaPila1(p1, p2) assert contenidaPila2(p1, p2) == r assert contenidaPila3(p1, p2) == r assert contenidaPila4(p1, p2) == r # La comprobación es # src> poetry run pytest -q contenidaPila.py # 1 passed in 0.40s |
La función contenidaPila recibe dos pilas, p1 y p2, y verifica si todos los elementos de la pila p1 son elementos de la pila p2. Utilizamos una estrategia recursiva para verificar cada elemento de p1 en p2.
Iniciamos la función verificando si p1 es vacía, en cuyo caso retornamos True ya que todos los elementos de una pila vacía son elementos de cualquier otra pila. Si p1 no es vacía, entonces verificamos si el primer elemento de p1, que es la cima de p1, está contenido en p2 utilizando la función pertenecePila. Si está contenido, continuamos verificando el resto de la pila, desapilando la cima y llamando recursivamente a contenidaPila con el resto de la pila y p2. Si en algún momento se encuentra un elemento de p1 que no está en p2, retorna False.