Menu Close

TAD de los conjuntos: Unión de varios conjuntos

José A. Alonso, ,

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
Leer más →

TAD de los conjuntos: Unión de dos conjuntos

José A. Alonso, ,

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
Leer más →

TAD de los conjuntos: Número de elementos de un conjunto

José A. Alonso, ,

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
Leer más →

TAD de los conjuntos: Conjunto unitario

José A. Alonso, ,

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())
Leer más →

TAD de los conjuntos: Reconocimiento de subconjunto propio

José A. Alonso, ,

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

   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

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


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
Leer más →