2-febrero-2023 – Exercitium

TAD de las pilas: Ordenación de pilas por inserción

PorJosé A. Alonso 2-febrero-202322-enero-2023

Utilizando el tipo abstracto de datos de las pilas, definir la función

   ordenaInserPila :: Ord a => Pila a -> Pila a

1	ordenaInserPila :: Ord a => Pila a -> Pila a

tal que ordenaInserPila p es la pila obtenida ordenando por inserción los los elementos de la pila p. Por ejemplo,

   λ> ordenaInserPila (apila 4 (apila 1 (apila 3 vacia)))
   1 | 3 | 4

1 2	λ> ordenaInserPila (apila 4 (apila 1 (apila 3 vacia))) 1 \| 3 \| 4

Comprobar con QuickCheck que la pila (ordenaInserPila p) está ordenada.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila)
import Transformaciones_pilas_listas (listaApila, pilaAlista)
import OrdenadaPila (ordenadaPila)
import Test.QuickCheck

-- 1ª solución
-- ===========

ordenaInserPila1 :: Ord a => Pila a -> Pila a
ordenaInserPila1 p
  | esVacia p = p
  | otherwise = insertaPila cp (ordenaInserPila1 dp)
  where cp = cima p
        dp = desapila p

insertaPila :: Ord a => a -> Pila a -> Pila a
insertaPila x p
  | esVacia p = apila x p
  | x < cp    = apila x p
  | otherwise = apila cp (insertaPila x dp)
  where cp = cima p
        dp = desapila p

-- 2ª solución
-- ===========

ordenaInserPila2 :: Ord a => Pila a -> Pila a
ordenaInserPila2  =
  listaApila . reverse . ordenaInserLista . pilaAlista

ordenaInserLista :: Ord a => [a] -> [a]
ordenaInserLista []      = []
ordenaInserLista (x: xs) = insertaLista x (ordenaInserLista xs)

insertaLista :: Ord a => a -> [a] -> [a]
insertaLista x [] = [x]
insertaLista x (y:ys) | x < y = x : y : ys
                      | otherwise = y : insertaLista x ys

-- Se usarán las funciones listaApila y pilaAlista del ejercicio
-- "Transformaciones entre pilas y listas" que se encuentra en
-- https://bit.ly/3ZHewQ8

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_ordenaInserPila :: Pila Int -> Bool
prop_ordenaInserPila p =
  ordenaInserPila1 p == ordenaInserPila2 p

-- La comprobación es
--    λ> quickCheck prop_ordenaInserPila
--    +++ OK, passed 100 tests.

-- Comprobación de la propiedad
-- ============================

-- Se usará la función ordenadaPila del ejercicio
-- "Reconocimiento de ordenación de pilas" que se encuentra en
-- https://bit.ly/3COqRbK

-- La propiedad es
prop_ordenadaOrdenaInserPila :: Pila Int -> Bool
prop_ordenadaOrdenaInserPila p =
  ordenadaPila (ordenaInserPila1 p)

-- La comprobación es
--    λ> quickCheck prop_ordenadaOrdenaInserPila
--    +++ OK, passed 100 tests.

import TAD.Pila (Pila, vacia, apila, esVacia, cima, desapila)

import Transformaciones_pilas_listas (listaApila, pilaAlista)

import OrdenadaPila (ordenadaPila)

import Test.QuickCheck

-- 1ª solución

-- ===========

ordenaInserPila1 :: Ord a => Pila a -> Pila a

ordenaInserPila1 p

| esVacia p = p

| otherwise = insertaPila cp (ordenaInserPila1 dp)

where cp = cima p

dp = desapila p

insertaPila :: Ord a => a -> Pila a -> Pila a

insertaPila x p

| esVacia p = apila x p

| x < cp = apila x p

| otherwise = apila cp (insertaPila x dp)

where cp = cima p

dp = desapila p

-- 2ª solución

-- ===========

ordenaInserPila2 :: Ord a => Pila a -> Pila a

ordenaInserPila2 =

listaApila . reverse . ordenaInserLista . pilaAlista

ordenaInserLista :: Ord a => [a] -> [a]

ordenaInserLista [] = []

ordenaInserLista (x: xs) = insertaLista x (ordenaInserLista xs)

insertaLista :: Ord a => a -> [a] -> [a]

insertaLista x [] = [x]

insertaLista x (y:ys) | x < y = x : y : ys

| otherwise = y : insertaLista x ys

-- Se usarán las funciones listaApila y pilaAlista del ejercicio

-- "Transformaciones entre pilas y listas" que se encuentra en

-- https://bit.ly/3ZHewQ8

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_ordenaInserPila :: Pila Int -> Bool

prop_ordenaInserPila p =

ordenaInserPila1 p == ordenaInserPila2 p

-- La comprobación es

-- λ> quickCheck prop_ordenaInserPila

-- +++ OK, passed 100 tests.

-- Comprobación de la propiedad

-- ============================

-- Se usará la función ordenadaPila del ejercicio

-- "Reconocimiento de ordenación de pilas" que se encuentra en

-- https://bit.ly/3COqRbK

-- La propiedad es

prop_ordenadaOrdenaInserPila :: Pila Int -> Bool

prop_ordenadaOrdenaInserPila p =

ordenadaPila (ordenaInserPila1 p)

-- La comprobación es

-- λ> quickCheck prop_ordenadaOrdenaInserPila

-- +++ OK, passed 100 tests.

Soluciones en Python

from copy import deepcopy
from typing import TypeVar

from hypothesis import given

from src.ordenadaPila import ordenadaPila
from src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria,
                          vacia)
from src.transformaciones_pilas_listas import listaApila, pilaAlista

A = TypeVar('A', int, float, str)

# 1ª solución
# ===========

def insertaPila(x: A, p: Pila[A]) -> Pila[A]:
    if esVacia(p):
        return apila(x, p)
    cp = cima(p)
    if x < cp:
        return apila(x, p)
    dp = desapila(p)
    return apila(cp, insertaPila(x, dp))

def ordenaInserPila1(p: Pila[A]) -> Pila[A]:
    if esVacia(p):
        return p
    cp = cima(p)
    dp = desapila(p)
    return insertaPila(cp, ordenaInserPila1(dp))

# 2ª solución
# ===========

# Se usarán las funciones listaApila y pilaAlista del ejercicio
# "Transformaciones entre pilas y listas" que se encuentra en
# https://bit.ly/3ZHewQ8

def insertaLista(x: A, ys: list[A]) -> list[A]:
    if not ys:
        return [x]
    if x < ys[0]:
        return [x] + ys
    return [ys[0]] + insertaLista(x, ys[1:])

def ordenaInserLista(xs: list[A]) -> list[A]:
    if not xs:
        return []
    return insertaLista(xs[0], ordenaInserLista(xs[1:]))

def ordenaInserPila2(p: Pila[A]) -> Pila[A]:
    return listaApila(list(reversed(ordenaInserLista(pilaAlista(p)))))

# 3ª solución
# ===========

def ordenaInserPila3Aux(p: Pila[A]) -> Pila[A]:
    if p.esVacia():
        return p
    cp = p.cima()
    p.desapila()
    return insertaPila(cp, ordenaInserPila3Aux(p))

def ordenaInserPila3(p: Pila[A]) -> Pila[A]:
    q = deepcopy(p)
    return ordenaInserPila3Aux(q)

# Comprobación de equivalencia de las definiciones
# ================================================

# La propiedad es
@given(p=pilaAleatoria())
def test_ordenaInserPila(p: Pila[int]) -> None:
    r = ordenaInserPila1(p)
    assert ordenaInserPila2(p) == r
    assert ordenaInserPila3(p) == r

# La comprobación es
#    src> poetry run pytest -q ordenaInserPila.py
#    1 passed in 0.31s

# Comprobación de la propiedad
# ============================

# Se usará la función ordenadaPila del ejercicio
# "Reconocimiento de ordenación de pilas" que se encuentra en
# https://bit.ly/3COqRbK

# La propiedad es
@given(p=pilaAleatoria())
def test_ordenadaOrdenaInserPila(p: Pila[int]) -> None:
    ordenadaPila(ordenaInserPila1(p))

# La comprobación es
#    src> poetry run pytest -q ordenaInserPila.py
#    2 passed in 0.47s

from copy import deepcopy

from typing import TypeVar

from hypothesis import given

from src.ordenadaPila import ordenadaPila

from src.TAD.pila import (Pila, apila, cima, desapila, esVacia, pilaAleatoria,

vacia)

from src.transformaciones_pilas_listas import listaApila, pilaAlista

A = TypeVar('A', int, float, str)

# 1ª solución

# ===========

def insertaPila(x: A, p: Pila[A]) -> Pila[A]:

if esVacia(p):

return apila(x, p)

cp = cima(p)

if x < cp:

return apila(x, p)

dp = desapila(p)

return apila(cp, insertaPila(x, dp))

def ordenaInserPila1(p: Pila[A]) -> Pila[A]:

if esVacia(p):

return p

cp = cima(p)

dp = desapila(p)

return insertaPila(cp, ordenaInserPila1(dp))

# 2ª solución

# ===========

# Se usarán las funciones listaApila y pilaAlista del ejercicio

# "Transformaciones entre pilas y listas" que se encuentra en

# https://bit.ly/3ZHewQ8

def insertaLista(x: A, ys: list[A]) -> list[A]:

if not ys:

return [x]

if x < ys[0]:

return [x] + ys

return [ys[0]] + insertaLista(x, ys[1:])

def ordenaInserLista(xs: list[A]) -> list[A]:

if not xs:

return []

return insertaLista(xs[0], ordenaInserLista(xs[1:]))

def ordenaInserPila2(p: Pila[A]) -> Pila[A]:

return listaApila(list(reversed(ordenaInserLista(pilaAlista(p)))))

# 3ª solución

# ===========

def ordenaInserPila3Aux(p: Pila[A]) -> Pila[A]:

if p.esVacia():

return p

cp = p.cima()

p.desapila()

return insertaPila(cp, ordenaInserPila3Aux(p))

def ordenaInserPila3(p: Pila[A]) -> Pila[A]:

q = deepcopy(p)

return ordenaInserPila3Aux(q)

# Comprobación de equivalencia de las definiciones

# ================================================

# La propiedad es

@given(p=pilaAleatoria())

def test_ordenaInserPila(p: Pila[int]) -> None:

r = ordenaInserPila1(p)

assert ordenaInserPila2(p) == r

assert ordenaInserPila3(p) == r

# La comprobación es

# src> poetry run pytest -q ordenaInserPila.py

# 1 passed in 0.31s

# Comprobación de la propiedad

# ============================

# Se usará la función ordenadaPila del ejercicio

# "Reconocimiento de ordenación de pilas" que se encuentra en

# https://bit.ly/3COqRbK

# La propiedad es

@given(p=pilaAleatoria())

def test_ordenadaOrdenaInserPila(p: Pila[int]) -> None:

ordenadaPila(ordenaInserPila1(p))

# La comprobación es

# src> poetry run pytest -q ordenaInserPila.py

# 2 passed in 0.47s

Día: 2-febrero-2023

TAD de las pilas: Ordenación de pilas por inserción

Entradas recientes

Buscar

Correo electrónico