marzo 2023 – Página 5

TAD de los conjuntos: Reconocimiento de subconjunto propio

PorJosé A. Alonso 3-marzo-202322-febrero-2023

Utilizando el tipo abstracto de datos de los conjuntos definir la función

   subconjuntoPropio :: Ord a => Conj a -> Conj a -> Bool

1	subconjuntoPropio :: Ord a => Conj a -> Conj a -> Bool

tal subconjuntoPropio c1 c2 se verifica si c1 es un subconjunto propio de c2. Por ejemplo,

   λ> ej1 = inserta 5 (inserta 2 vacio)
   λ> ej2 = inserta 3 (inserta 2 (inserta 5 vacio))
   λ> ej3 = inserta 3 (inserta 4 (inserta 5 vacio))
   λ> ej4 = inserta 2 (inserta 5 vacio)
   λ> subconjuntoPropio ej1 ej2
   True
   λ> subconjuntoPropio ej1 ej3
   False
   λ> subconjuntoPropio ej1 ej4
   False

λ> ej1 = inserta 5 (inserta 2 vacio)

λ> ej2 = inserta 3 (inserta 2 (inserta 5 vacio))

λ> ej3 = inserta 3 (inserta 4 (inserta 5 vacio))

λ> ej4 = inserta 2 (inserta 5 vacio)

λ> subconjuntoPropio ej1 ej2

True

λ> subconjuntoPropio ej1 ej3

False

λ> subconjuntoPropio ej1 ej4

False

Soluciones

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

Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta)
import TAD_subconjunto (subconjunto)

subconjuntoPropio :: Ord a => Conj a -> Conj a -> Bool
subconjuntoPropio c1 c2 =
  subconjunto c1 c2 && c1 /= c2

-- La función subconjunto está definida en el ejercicio
-- "Reconocimiento de subconjuntos" que se encuentra en
-- https://bit.ly/3wPBtU5

import TAD.Conjunto (Conj, vacio, inserta)

import TAD_subconjunto (subconjunto)

subconjuntoPropio :: Ord a => Conj a -> Conj a -> Bool

subconjuntoPropio c1 c2 =

subconjunto c1 c2 && c1 /= c2

-- La función subconjunto está definida en el ejercicio

-- "Reconocimiento de subconjuntos" que se encuentra en

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

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from typing import Protocol, TypeVar

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
                              inserta, menor, pertenece, vacio)
from src.TAD_subconjunto import subconjunto

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

def subconjuntoPropio(c1: Conj[A], c2: Conj[A]) -> bool:
    return subconjunto(c1, c2) and c1 != c2

# La función subconjunto está definida en el ejercicio
# "Reconocimiento de subconjuntos" que se encuentra en
# https://bit.ly/3wPBtU5

from __future__ import annotations

from abc import abstractmethod

from typing import Protocol, TypeVar

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,

inserta, menor, pertenece, vacio)

from src.TAD_subconjunto import subconjunto

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

def subconjuntoPropio(c1: Conj[A], c2: Conj[A]) -> bool:

return subconjunto(c1, c2) and c1 != c2

# La función subconjunto está definida en el ejercicio

# "Reconocimiento de subconjuntos" que se encuentra en

# https://bit.ly/3wPBtU5

TAD de los conjuntos: Reconocimiento de subconjuntos

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

Utilizando el tipo abstracto de datos de los conjuntos definir la función

   subconjunto :: Ord a => Conj a -> Conj a -> Bool

1	subconjunto :: Ord a => Conj a -> Conj a -> Bool

tal que subconjunto c1 c2 se verifica si todos los elementos de c1 pertenecen a c2. Por ejemplo,

   λ> ej1 = inserta 5 (inserta 2 vacio)
   λ> ej2 = inserta 3 (inserta 2 (inserta 5 vacio))
   λ> ej3 = inserta 3 (inserta 4 (inserta 5 vacio))
   λ> subconjunto ej1 ej2
   True
   λ> subconjunto ej1 ej3
   False

λ> ej1 = inserta 5 (inserta 2 vacio)

λ> ej2 = inserta 3 (inserta 2 (inserta 5 vacio))

λ> ej3 = inserta 3 (inserta 4 (inserta 5 vacio))

λ> subconjunto ej1 ej2

True

λ> subconjunto ej1 ej3

False

Soluciones

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

Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, pertenece, esVacio)
import Transformaciones_conjuntos_listas (conjuntoAlista)
import Test.QuickCheck

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

subconjunto :: Ord a => Conj a -> Conj a -> Bool
subconjunto c1 c2
  | esVacio c1 = True
  | otherwise  =  pertenece mc1 c2 && subconjunto rc1 c2
  where mc1 = menor c1
        rc1 = elimina mc1 c1

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

subconjunto2 :: Ord a => Conj a -> Conj a -> Bool
subconjunto2 c1 c2 =
  and [pertenece x c2 | x <- conjuntoAlista c1]

-- La función conjuntoAlista está definida en el ejercicio
-- "Transformaciones entre conjuntos y listas" que se encuentra en
-- https://bit.ly/3RexzxH

-- 3ª solución
-- ===========

subconjunto3 :: Ord a => Conj a -> Conj a -> Bool
subconjunto3 c1 c2 =
  all (`pertenece` c2) (conjuntoAlista c1)

-- 4ª solución
-- ===========

subconjunto4 :: Ord a => Conj a -> Conj a -> Bool
subconjunto4 c1 c2 =
  sublista (conjuntoAlista c1) (conjuntoAlista c2)

-- (sublista xs ys) se verifica si xs es una sublista de ys. Por
-- ejemplo,
--    sublista [5, 2] [3, 2, 5]  ==  True
--    sublista [5, 2] [3, 4, 5]  ==  False
sublista :: Ord a => [a] -> [a] -> Bool
sublista [] _      = True
sublista (x:xs) ys = elem x ys && sublista xs ys

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

-- La propiedad es
prop_subconjunto :: Conj Int -> Conj Int -> Bool
prop_subconjunto c1 c2 =
  all (== subconjunto c1 c2)
      [subconjunto2 c1 c2,
       subconjunto3 c1 c2,
       subconjunto4 c1 c2]

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

import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, pertenece, esVacio)

import Transformaciones_conjuntos_listas (conjuntoAlista)

import Test.QuickCheck

-- 1ª solución

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

subconjunto :: Ord a => Conj a -> Conj a -> Bool

subconjunto c1 c2

| esVacio c1 = True

| otherwise = pertenece mc1 c2 && subconjunto rc1 c2

where mc1 = menor c1

rc1 = elimina mc1 c1

-- 2ª solución

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

subconjunto2 :: Ord a => Conj a -> Conj a -> Bool

subconjunto2 c1 c2 =

and [pertenece x c2 | x <- conjuntoAlista c1]

-- La función conjuntoAlista está definida en el ejercicio

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

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

-- 3ª solución

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

subconjunto3 :: Ord a => Conj a -> Conj a -> Bool

subconjunto3 c1 c2 =

all (`pertenece` c2) (conjuntoAlista c1)

-- 4ª solución

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

subconjunto4 :: Ord a => Conj a -> Conj a -> Bool

subconjunto4 c1 c2 =

sublista (conjuntoAlista c1) (conjuntoAlista c2)

-- (sublista xs ys) se verifica si xs es una sublista de ys. Por

-- ejemplo,

-- sublista [5, 2] [3, 2, 5] == True

-- sublista [5, 2] [3, 4, 5] == False

sublista :: Ord a => [a] -> [a] -> Bool

sublista [] _ = True

sublista (x:xs) ys = elem x ys && sublista xs ys

-- Comprobación de equivalencia

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

-- La propiedad es

prop_subconjunto :: Conj Int -> Conj Int -> Bool

prop_subconjunto c1 c2 =

all (== subconjunto c1 c2)

[subconjunto2 c1 c2,

subconjunto3 c1 c2,

subconjunto4 c1 c2]

-- La comprobación es

-- λ> quickCheck prop_subconjunto

-- +++ OK, passed 100 tests.

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from copy import deepcopy
from typing import Protocol, TypeVar

from hypothesis import given

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
                              inserta, menor, pertenece, vacio)
from src.TAD_Transformaciones_conjuntos_listas import conjuntoAlista

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

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

def subconjunto(c1: Conj[A], c2: Conj[A]) -> bool:
    if esVacio(c1):
        return True
    mc1 = menor(c1)
    rc1 = elimina(mc1, c1)
    return pertenece(mc1, c2) and subconjunto(rc1, c2)

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

def subconjunto2(c1: Conj[A], c2: Conj[A]) -> bool:
    return all((pertenece(x, c2) for x in conjuntoAlista(c1)))

# La función conjuntoAlista está definida en el ejercicio
# "Transformaciones entre conjuntos y listas" que se encuentra en
# https://bit.ly/3RexzxH

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

# (sublista xs ys) se verifica si xs es una sublista de ys. Por
# ejemplo,
#    sublista [5, 2] [3, 2, 5]  ==  True
#    sublista [5, 2] [3, 4, 5]  ==  False
def sublista(xs: list[A], ys: list[A]) -> bool:
    if not xs:
        return True
    return xs[0] in ys and sublista(xs[1:], ys)

def subconjunto3(c1: Conj[A], c2: Conj[A]) -> bool:
    return sublista(conjuntoAlista(c1), conjuntoAlista(c2))

# 4ª solución
# ===========

def subconjunto4(c1: Conj[A], c2: Conj[A]) -> bool:
    while not esVacio(c1):
        mc1 = menor(c1)
        if not pertenece(mc1, c2):
            return False
        c1 = elimina(mc1, c1)
    return True

# 5ª solución
# ===========

def subconjunto5Aux(c1: Conj[A], c2: Conj[A]) -> bool:
    while not c1.esVacio():
        mc1 = c1.menor()
        if not c2.pertenece(mc1):
            return False
        c1.elimina(mc1)
    return True

def subconjunto5(c1: Conj[A], c2: Conj[A]) -> bool:
    _c1 = deepcopy(c1)
    return subconjunto5Aux(_c1, c2)

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())
def test_subconjunto(c1: Conj[int], c2: Conj[int]) -> None:
    r = subconjunto(c1, c2)
    assert subconjunto2(c1, c2) == r
    assert subconjunto3(c1, c2) == r
    assert subconjunto4(c1, c2) == r
    assert subconjunto5(c1, c2) == r

# La comprobación de las propiedades es
#    > poetry run pytest -q TAD_subconjunto.py
#    1 passed in 0.37s

from __future__ import annotations

from abc import abstractmethod

from copy import deepcopy

from typing import Protocol, TypeVar

from hypothesis import given

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,

inserta, menor, pertenece, vacio)

from src.TAD_Transformaciones_conjuntos_listas import conjuntoAlista

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

# 1ª solución

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

def subconjunto(c1: Conj[A], c2: Conj[A]) -> bool:

if esVacio(c1):

return True

mc1 = menor(c1)

rc1 = elimina(mc1, c1)

return pertenece(mc1, c2) and subconjunto(rc1, c2)

# 2ª solución

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

def subconjunto2(c1: Conj[A], c2: Conj[A]) -> bool:

return all((pertenece(x, c2) for x in conjuntoAlista(c1)))

# La función conjuntoAlista está definida en el ejercicio

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

# https://bit.ly/3RexzxH

# 3ª solución

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

# (sublista xs ys) se verifica si xs es una sublista de ys. Por

# ejemplo,

# sublista [5, 2] [3, 2, 5] == True

# sublista [5, 2] [3, 4, 5] == False

def sublista(xs: list[A], ys: list[A]) -> bool:

if not xs:

return True

return xs[0] in ys and sublista(xs[1:], ys)

def subconjunto3(c1: Conj[A], c2: Conj[A]) -> bool:

return sublista(conjuntoAlista(c1), conjuntoAlista(c2))

# 4ª solución

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

def subconjunto4(c1: Conj[A], c2: Conj[A]) -> bool:

while not esVacio(c1):

mc1 = menor(c1)

if not pertenece(mc1, c2):

return False

c1 = elimina(mc1, c1)

return True

# 5ª solución

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

def subconjunto5Aux(c1: Conj[A], c2: Conj[A]) -> bool:

while not c1.esVacio():

mc1 = c1.menor()

if not c2.pertenece(mc1):

return False

c1.elimina(mc1)

return True

def subconjunto5(c1: Conj[A], c2: Conj[A]) -> bool:

_c1 = deepcopy(c1)

return subconjunto5Aux(_c1, c2)

# Comprobación de equivalencia

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

# La propiedad es

@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())

def test_subconjunto(c1: Conj[int], c2: Conj[int]) -> None:

r = subconjunto(c1, c2)

assert subconjunto2(c1, c2) == r

assert subconjunto3(c1, c2) == r

assert subconjunto4(c1, c2) == r

assert subconjunto5(c1, c2) == r

# La comprobación de las propiedades es

# > poetry run pytest -q TAD_subconjunto.py

# 1 passed in 0.37s

TAD de los conjuntos: Transformaciones entre conjuntos y listas

PorJosé A. Alonso 1-marzo-202322-febrero-2023

Utilizando el tipo abstracto de datos de los conjuntos definir las funciones

   listaAconjunto :: [a] -> Conj a
   conjuntoAlista :: Conj a -> [a]

1 2	listaAconjunto :: [a] -> Conj a conjuntoAlista :: Conj a -> [a]

tales que
+ listaAconjunto xs es el conjunto formado por los elementos de xs. Por ejemplo,

     λ> listaAconjunto [3, 2, 5]
     {2, 3, 5}

1 2	λ> listaAconjunto [3, 2, 5] {2, 3, 5}

conjuntoAlista c es la lista formada por los elementos del conjunto c. Por ejemplo,

     λ> conjuntoAlista (inserta 5 (inserta 2 (inserta 3 vacio)))
     [2,3,5]

1 2	λ> conjuntoAlista (inserta 5 (inserta 2 (inserta 3 vacio))) [2,3,5]

Comprobar con QuickCheck que ambas funciones son inversa; es decir,

   conjuntoAlista (listaAconjunto xs) = sort (nub xs)
   listaAconjunto (conjuntoAlista c)  = c

1 2	conjuntoAlista (listaAconjunto xs) = sort (nub xs) listaAconjunto (conjuntoAlista c) = c

Soluciones

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

Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, pertenece, esVacio)
import Data.List (sort, nub)
import Test.QuickCheck

-- 1ª definición de listaAconjunto
-- ===============================

listaAconjunto :: Ord a => [a] -> Conj a
listaAconjunto []     = vacio
listaAconjunto (x:xs) = inserta x (listaAconjunto xs)

-- 2ª definición de listaAconjunto
-- ===============================

listaAconjunto2 :: Ord a => [a] -> Conj a
listaAconjunto2 = foldr inserta vacio

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

-- La propiedad es
prop_listaAconjunto :: [Int] -> Bool
prop_listaAconjunto xs =
  listaAconjunto xs == listaAconjunto2 xs

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

-- Definición de conjuntoAlista
-- ============================

conjuntoAlista :: Ord a => Conj a -> [a]
conjuntoAlista c
  | esVacio c = []
  | otherwise = mc : conjuntoAlista rc
  where mc = menor c
        rc = elimina mc c

-- Comprobación de las propiedades
-- ===============================

-- La primera propiedad es
prop_1_listaAconjunto :: [Int] -> Bool
prop_1_listaAconjunto xs =
  conjuntoAlista (listaAconjunto xs) == sort (nub xs)

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

-- La segunda propiedad es
prop_2_listaAconjunto :: Conj Int -> Bool
prop_2_listaAconjunto c =
  listaAconjunto (conjuntoAlista c) == c

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

import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, pertenece, esVacio)

import Data.List (sort, nub)

import Test.QuickCheck

-- 1ª definición de listaAconjunto

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

listaAconjunto :: Ord a => [a] -> Conj a

listaAconjunto [] = vacio

listaAconjunto (x:xs) = inserta x (listaAconjunto xs)

-- 2ª definición de listaAconjunto

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

listaAconjunto2 :: Ord a => [a] -> Conj a

listaAconjunto2 = foldr inserta vacio

-- Comprobación de equivalencia

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

-- La propiedad es

prop_listaAconjunto :: [Int] -> Bool

prop_listaAconjunto xs =

listaAconjunto xs == listaAconjunto2 xs

-- La comprobación es

-- λ> quickCheck prop_listaAconjunto

-- +++ OK, passed 100 tests.

-- Definición de conjuntoAlista

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

conjuntoAlista :: Ord a => Conj a -> [a]

conjuntoAlista c

| esVacio c = []

| otherwise = mc : conjuntoAlista rc

where mc = menor c

rc = elimina mc c

-- Comprobación de las propiedades

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

-- La primera propiedad es

prop_1_listaAconjunto :: [Int] -> Bool

prop_1_listaAconjunto xs =

conjuntoAlista (listaAconjunto xs) == sort (nub xs)

-- La comprobación es

-- λ> quickCheck prop_1_listaAconjunto

-- +++ OK, passed 100 tests.

-- La segunda propiedad es

prop_2_listaAconjunto :: Conj Int -> Bool

prop_2_listaAconjunto c =

listaAconjunto (conjuntoAlista c) == c

-- La comprobación es

-- λ> quickCheck prop_2_listaAconjunto

-- +++ OK, passed 100 tests.

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from copy import deepcopy
from functools import reduce
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, pertenece, vacio)

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

# 1ª definición de listaAconjunto
# ===============================

def listaAconjunto(xs: list[A]) -> Conj[A]:
    if not xs:
        return vacio()
    return inserta(xs[0], listaAconjunto(xs[1:]))

# 2ª definición de listaAconjunto
# ===============================

def listaAconjunto2(xs: list[A]) -> Conj[A]:
    return reduce(lambda ys, y: inserta(y, ys), xs, vacio())

# 3ª solución de listaAconjunto
# =============================

def listaAconjunto3(xs: list[A]) -> Conj[A]:
    c: Conj[A] = Conj()
    for x in xs:
        c.inserta(x)
    return c

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.lists(st.integers()))
def test_listaAconjunto(xs: list[int]) -> None:
    r = listaAconjunto(xs)
    assert listaAconjunto2(xs) == r
    assert listaAconjunto3(xs) == r

# 1ª definición de conjuntoAlista
# ===============================

def conjuntoAlista(c: Conj[A]) -> list[A]:
    if esVacio(c):
        return []
    mc = menor(c)
    rc = elimina(mc, c)
    return [mc] + conjuntoAlista(rc)

# 2ª definición de conjuntoAlista
# ===============================

def conjuntoAlista2Aux(c: Conj[A]) -> list[A]:
    if c.esVacio():
        return []
    mc = c.menor()
    c.elimina(mc)
    return [mc] + conjuntoAlista2Aux(c)

def conjuntoAlista2(c: Conj[A]) -> list[A]:
    c1 = deepcopy(c)
    return conjuntoAlista2Aux(c1)

# 3ª definición de conjuntoAlista
# ===============================

def conjuntoAlista3Aux(c: Conj[A]) -> list[A]:
    r = []
    while not c.esVacio():
        mc = c.menor()
        r.append(mc)
        c.elimina(mc)
    return r

def conjuntoAlista3(c: Conj[A]) -> list[A]:
    c1 = deepcopy(c)
    return conjuntoAlista3Aux(c1)

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

@given(c=conjuntoAleatorio())
def test_conjuntoAlista(c: Conj[int]) -> None:
    r = conjuntoAlista(c)
    assert conjuntoAlista2(c) == r
    assert conjuntoAlista3(c) == r

# Comprobación de las propiedades
# ===============================

# La primera propiedad es
@given(st.lists(st.integers()))
def test_1_listaAconjunto(xs: list[int]) -> None:
    assert conjuntoAlista(listaAconjunto(xs)) == sorted(list(set(xs)))

# La segunda propiedad es
@given(c=conjuntoAleatorio())
def test_2_listaAconjunto(c: Conj[int]) -> None:
    assert listaAconjunto(conjuntoAlista(c)) == c

# La comprobación de las propiedades es
#    > poetry run pytest -v TAD_Transformaciones_conjuntos_listas.py
#       test_listaAconjunto PASSED
#       test_conjuntoAlista PASSED
#       test_1_listaAconjunto PASSED
#       test_2_listaAconjunto PASSED

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

from __future__ import annotations

from abc import abstractmethod

from copy import deepcopy

from functools import reduce

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, pertenece, vacio)

class Comparable(Protocol):

@abstractmethod

def __lt__(self: A, otro: A) -> bool:

pass

A = TypeVar('A', bound=Comparable)

# 1ª definición de listaAconjunto

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

def listaAconjunto(xs: list[A]) -> Conj[A]:

if not xs:

return vacio()

return inserta(xs[0], listaAconjunto(xs[1:]))

# 2ª definición de listaAconjunto

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

def listaAconjunto2(xs: list[A]) -> Conj[A]:

return reduce(lambda ys, y: inserta(y, ys), xs, vacio())

# 3ª solución de listaAconjunto

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

def listaAconjunto3(xs: list[A]) -> Conj[A]:

c: Conj[A] = Conj()

for x in xs:

c.inserta(x)

return c

# Comprobación de equivalencia

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

# La propiedad es

@given(st.lists(st.integers()))

def test_listaAconjunto(xs: list[int]) -> None:

r = listaAconjunto(xs)

assert listaAconjunto2(xs) == r

assert listaAconjunto3(xs) == r

# 1ª definición de conjuntoAlista

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

def conjuntoAlista(c: Conj[A]) -> list[A]:

if esVacio(c):

return []

mc = menor(c)

rc = elimina(mc, c)

return [mc] + conjuntoAlista(rc)

# 2ª definición de conjuntoAlista

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

def conjuntoAlista2Aux(c: Conj[A]) -> list[A]:

if c.esVacio():

return []

mc = c.menor()

c.elimina(mc)

return [mc] + conjuntoAlista2Aux(c)

def conjuntoAlista2(c: Conj[A]) -> list[A]:

c1 = deepcopy(c)

return conjuntoAlista2Aux(c1)

# 3ª definición de conjuntoAlista

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

def conjuntoAlista3Aux(c: Conj[A]) -> list[A]:

r = []

while not c.esVacio():

mc = c.menor()

r.append(mc)

c.elimina(mc)

return r

def conjuntoAlista3(c: Conj[A]) -> list[A]:

c1 = deepcopy(c)

return conjuntoAlista3Aux(c1)

# Comprobación de equivalencia de las definiciones de conjuntoAlista

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

@given(c=conjuntoAleatorio())

def test_conjuntoAlista(c: Conj[int]) -> None:

r = conjuntoAlista(c)

assert conjuntoAlista2(c) == r

assert conjuntoAlista3(c) == r

# Comprobación de las propiedades

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

# La primera propiedad es

@given(st.lists(st.integers()))

def test_1_listaAconjunto(xs: list[int]) -> None:

assert conjuntoAlista(listaAconjunto(xs)) == sorted(list(set(xs)))

# La segunda propiedad es

@given(c=conjuntoAleatorio())

def test_2_listaAconjunto(c: Conj[int]) -> None:

assert listaAconjunto(conjuntoAlista(c)) == c

# La comprobación de las propiedades es

# > poetry run pytest -v TAD_Transformaciones_conjuntos_listas.py

# test_listaAconjunto PASSED

# test_conjuntoAlista PASSED

# test_1_listaAconjunto PASSED

# test_2_listaAconjunto PASSED

Meses: marzo 2023

TAD de los conjuntos: Reconocimiento de subconjunto propio

TAD de los conjuntos: Reconocimiento de subconjuntos

TAD de los conjuntos: Transformaciones entre conjuntos y listas

Entradas recientes

Buscar

Correo electrónico