Menu Close

La semana en Exercitium (11 de marzo de 2023)

José A. Alonso-

Esta semana he publicado en Exercitium las soluciones de los siguientes problemas sobre el tipo abstracto de datos de los conjuntos:

A continuación se muestran las soluciones.

1. Conjunto unitario

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

   unitario :: Ord a => a -> Conj a

tal que unitario x es el conjunto {x}. Por ejemplo,

   unitario 5 == {5}

Soluciones

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


Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta)
 
unitario :: Ord a => a -> Conj a
unitario x = inserta x vacio


Soluciones en Python

from __future__ import annotations
 
from abc import abstractmethod
from typing import Protocol, TypeVar
 
from src.TAD.conjunto import Conj, inserta, vacio
 
class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass
 
A = TypeVar('A', bound=Comparable)
 
def unitario(x: A) -> Conj[A]:
    return inserta(x, vacio())

2. Número de elementos de un conjunto

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

   cardinal :: Conj a -> Int

tal que cardinal c es el número de elementos del conjunto c. Por ejemplo,

   cardinal (inserta 4 (inserta 5 vacio))             == 2
   cardinal (inserta 4 (inserta 5 (inserta 4 vacio))) == 2

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, esVacio)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
cardinal :: Ord a => Conj a -> Int
cardinal c
  | esVacio c = 0
  | otherwise = 1 + cardinal (elimina (menor c) c)
 
-- 2ª solución
-- ===========
 
cardinal2 :: Ord a => Conj a -> Int
cardinal2 = length . conjuntoAlista
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_cardinal :: Conj Int -> Bool
prop_cardinal c =
  cardinal c == cardinal2 c
 
-- La comprobación es
--    λ> quickCheck prop_cardinal
--    +++ 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, 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 cardinal(c: Conj[A]) -> int:
    if esVacio(c):
        return 0
    return 1 + cardinal(elimina(menor(c), c))
 
# 2ª solución
# ===========
 
def cardinal2(c: Conj[A]) -> int:
    return len(conjuntoAlista(c))
 
# 3ª solución
# ===========
 
def cardinal3(c: Conj[A]) -> int:
    r = 0
    while not esVacio(c):
        r = r + 1
        c = elimina(menor(c), c)
    return r
 
# 4ª solución
# ===========
 
def cardinal4Aux(c: Conj[A]) -> int:
    r = 0
    while not c.esVacio():
        r = r + 1
        c.elimina(menor(c))
    return r
 
def cardinal4(c: Conj[A]) -> int:
    _c = deepcopy(c)
    return cardinal4Aux(_c)
 
# Comprobación de equivalencia
# ============================
 
@given(c=conjuntoAleatorio())
def test_cardinal(c: Conj[int]) -> None:
    r = cardinal(c)
    assert cardinal2(c) == r
    assert cardinal3(c) == r
    assert cardinal3(c) == r
 
# La comprobación es
#    src> poetry run pytest -q TAD_Numero_de_elementos_de_un_conjunto.py
#    1 passed in 0.33s

3. Unión de dos conjuntos

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

   union :: Ord a => Conj a -> Conj a -> Conj a

tal union c1 c2 es la unión de ambos conjuntos. Por ejemplo,

   λ> ej1 = inserta 3 (inserta 5 vacio)
   λ> ej2 = inserta 4 (inserta 3 vacio)
   λ> union ej1 ej2
   {3, 4, 5}

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, esVacio)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)
import qualified Data.List as L (union)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
union :: Ord a => Conj a -> Conj a -> Conj a
union c1 c2
  | esVacio c1 = c2
  | otherwise  = inserta mc1 (rc1 `union` c2)
  where mc1 = menor c1
        rc1 = elimina mc1 c1
 
-- 2ª solución
-- ===========
 
union2 :: Ord a => Conj a -> Conj a -> Conj a
union2 c1 c2 =
  foldr inserta c2 (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
-- ===========
 
union3 :: Ord a => Conj a -> Conj a -> Conj a
union3 c1 c2 =
  listaAconjunto (conjuntoAlista c1 `L.union` conjuntoAlista c2)
 
-- La función listaAconjunto está definida en el ejercicio
-- "Transformaciones entre conjuntos y listas" que se encuentra en
-- https://bit.ly/3RexzxH
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_union :: Conj Int -> Conj Int -> Bool
prop_union c1 c2 =
  all (== union c1 c2)
      [union2 c1 c2,
       union3 c1 c2]
 
-- La comprobación es
--    λ> quickCheck prop_union
--    +++ 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 src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
                              inserta, menor, 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 union(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    if esVacio(c1):
        return c2
    mc1 = menor(c1)
    rc1 = elimina(mc1, c1)
    return inserta(mc1, union(rc1, c2))
 
# 2ª solución
# ===========
 
def union2(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    return reduce(lambda c, x: inserta(x, c), conjuntoAlista(c1), c2)
 
# 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
# ===========
 
def union3(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    r = c2
    while not esVacio(c1):
        mc1 = menor(c1)
        r = inserta(mc1, r)
        c1 = elimina(mc1, c1)
    return r
 
# 4ª solución
# ===========
 
def union4Aux(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    while not c1.esVacio():
        mc1 = menor(c1)
        c2.inserta(mc1)
        c1.elimina(mc1)
    return c2
 
def union4(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    _c1 = deepcopy(c1)
    _c2 = deepcopy(c2)
    return union4Aux(_c1, _c2)
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())
def test_union(c1: Conj[int], c2: Conj[int]) -> None:
    r = union(c1, c2)
    assert union2(c1, c2) == r
    assert union3(c1, c2) == r
    assert union4(c1, c2) == r
 
# La comprobación de las propiedades es
#    > poetry run pytest -q TAD_Union_de_dos_conjuntos.py
#    1 passed in 0.35s

4. Unión de varios conjuntos

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

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

tal unionG cs calcule la unión de la lista de conjuntos cs. Por ejemplo,

   λ> ej1 = inserta 3 (inserta 5 vacio)
   λ> ej2 = inserta 5 (inserta 6 vacio)
   λ> ej3 = inserta 3 (inserta 6 vacio)
   λ> unionG [ej1, ej2, ej3]
   {3, 5, 6}

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_Union_de_dos_conjuntos (union)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
unionG :: Ord a => [Conj a] -> Conj a
unionG []          = vacio
unionG (c:cs) = c `union` unionG cs
 
-- La función union está definida en el ejercicio
-- "Unión de dos conjuntos" que se encuentra en
-- https://bit.ly/3Y1jBl8
 
-- 2ª solución
-- ===========
 
unionG2 :: Ord a => [Conj a] -> Conj a
unionG2 = foldr union vacio
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_unionG :: [Conj Int] -> Bool
prop_unionG cs =
  unionG cs == unionG2 cs
 
-- La comprobación es
--    λ> quickCheck prop_unionG
--    +++ OK, passed 100 tests.


Soluciones en Python

from __future__ import annotations
 
from abc import abstractmethod
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, inserta, vacio
from src.TAD_Union_de_dos_conjuntos import union
 
class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass
 
A = TypeVar('A', bound=Comparable)
 
# 1ª solución
# ===========
 
def unionG(cs: list[Conj[A]]) -> Conj[A]:
    if not cs:
        return vacio()
    return union(cs[0], unionG(cs[1:]))
 
# La función union está definida en el ejercicio
# "Unión de dos conjuntos" que se encuentra en
# https://bit.ly/3Y1jBl8
 
# 2ª solución
# ===========
 
def unionG2(cs: list[Conj[A]]) -> Conj[A]:
    return reduce(union, cs, vacio())
 
# 3ª solución
# ===========
 
def unionG3(cs: list[Conj[A]]) -> Conj[A]:
    r: Conj[A] = vacio()
    for c in cs:
        r = union(c, r)
    return r
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.lists(conjuntoAleatorio(), max_size=10))
def test_union(cs: list[Conj[int]]) -> None:
    r = unionG(cs)
    assert unionG2(cs) == r
    assert unionG3(cs) == r
 
# La comprobación de las propiedades es
#    > poetry run pytest -q TAD_Union_de_varios_conjuntos.py
#    1 passed in 0.75s

5. Intersección de dos conjuntos

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

   interseccion :: Ord a => Conj a -> Conj a -> Conj a

tal que interseccion c1 c2 es la intersección de los conjuntos c1 y c2. Por ejemplo,

   λ> ej1 = inserta 3 (inserta 5 (inserta 2 vacio))
   λ> ej2 = inserta 2 (inserta 4 (inserta 3 vacio))
   λ> interseccion ej1 ej2
   {2, 3}

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 TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)
import Data.List (intersect)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
interseccion :: Ord a => Conj a -> Conj a -> Conj a
interseccion c1 c2
  | esVacio c1       = vacio
  | pertenece mc1 c2 = inserta mc1 (interseccion rc1 c2)
  | otherwise        = interseccion rc1 c2
  where mc1 = menor c1
        rc1 = elimina mc1 c1
 
-- 2ª solución
-- ===========
 
interseccion2 :: Ord a => Conj a -> Conj a -> Conj a
interseccion2 c1 c2 =
  listaAconjunto [x | x <- conjuntoAlista c1, x `pertenece` c2]
 
-- Las funciones conjuntoAlista y listaAconjunto está definida en el
-- ejercicio Transformaciones entre conjuntos y listas" que se encuentra
-- en https://bit.ly/3RexzxH
 
-- 3ª solución
-- ===========
 
interseccion3 :: Ord a => Conj a -> Conj a -> Conj a
interseccion3 c1 c2 =
  listaAconjunto (conjuntoAlista c1 `intersect` conjuntoAlista c2)
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_interseccion :: Conj Int -> Conj Int -> Bool
prop_interseccion c1 c2 =
  all (== interseccion c1 c2)
      [interseccion2 c1 c2,
       interseccion3 c1 c2]
 
-- La comprobación es
--    λ> quickCheck prop_interseccion
--    +++ 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,
                                                       listaAconjunto)
 
class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass
 
A = TypeVar('A', bound=Comparable)
 
# 1ª solución
# ===========
 
def interseccion(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    if esVacio(c1):
        return vacio()
    mc1 = menor(c1)
    rc1 = elimina(mc1, c1)
    if pertenece(mc1, c2):
        return inserta(mc1, interseccion(rc1, c2))
    return interseccion(rc1, c2)
 
# 2ª solución
# ===========
 
def interseccion2(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    return listaAconjunto([x for x in conjuntoAlista(c1)
                           if pertenece(x, c2)])
#
# Las funciones conjuntoAlista y listaAconjunto está definida en el
# ejercicio Transformaciones entre conjuntos y listas" que se encuentra
# en https://bit.ly/3RexzxH
 
# 3ª solución
# ===========
 
def interseccion3(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    r: Conj[A] = vacio()
    while not esVacio(c1):
        mc1 = menor(c1)
        c1 = elimina(mc1, c1)
        if pertenece(mc1, c2):
            r = inserta(mc1, r)
    return r
 
# 4ª solución
# ===========
 
def interseccion4Aux(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    r: Conj[A] = vacio()
    while not c1.esVacio():
        mc1 = c1.menor()
        c1.elimina(mc1)
        if c2.pertenece(mc1):
            r.inserta(mc1)
    return r
 
def interseccion4(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    _c1 = deepcopy(c1)
    return interseccion4Aux(_c1, c2)
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())
def test_interseccion(c1: Conj[int], c2: Conj[int]) -> None:
    r = interseccion(c1, c2)
    assert interseccion2(c1, c2) == r
    assert interseccion3(c1, c2) == r
    assert interseccion4(c1, c2) == r
 
# La comprobación de las propiedades es
#    > poetry run pytest -q TAD_Interseccion_de_dos_conjuntos.py
#    1 passed in 0.30s
Sin categoría