Menu Close

TAD de los conjuntos: Conjuntos disjuntos

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

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

tal que disjuntos c1 c2 se verifica si los conjuntos c1 y c2 son disjuntos. Por ejemplo,

   λ> ej1 = inserta 2 (inserta 5 vacio)
   λ> ej2 = inserta 4 (inserta 3 vacio)
   λ> ej3 = inserta 5 (inserta 3 vacio)
   λ> disjuntos ej1 ej2
   True
   λ> disjuntos 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, esVacio, menor, elimina, pertenece)
import TAD_Interseccion_de_dos_conjuntos (interseccion)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
disjuntos :: Ord a => Conj a -> Conj a -> Bool
disjuntos c1 c2 = esVacio (interseccion c1 c2)
 
-- La función interseccion está definida en el ejercicio
-- "Intersección de dos conjuntos" que se encuentra en
-- https://bit.ly/3jDL9xZ
 
-- 2ª solución
-- ===========
 
disjuntos2 :: Ord a => Conj a -> Conj a -> Bool
disjuntos2 c1 c2
  | esVacio c1 = True
  | pertenece mc1 c2 = False
  | otherwise        = disjuntos2 rc1 c2
  where mc1 = menor c1
        rc1 = elimina mc1 c1
 
-- 3ª solución
-- ===========
 
disjuntos3 :: Ord a => Conj a -> Conj a -> Bool
disjuntos3 c1 c2 =
  all (`notElem` ys) xs
  where xs = conjuntoAlista c1
        ys = conjuntoAlista c2
 
-- La función conjuntoAlista 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_disjuntos :: Conj Int -> Conj Int -> Bool
prop_disjuntos c1 c2 =
  all (== disjuntos c1 c2)
      [disjuntos2 c1 c2,
       disjuntos3 c1 c2]
 
-- La comprobación es
--    λ> quickCheck prop_disjuntos
--    +++ 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_Interseccion_de_dos_conjuntos import interseccion
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 disjuntos(c1: Conj[A], c2: Conj[A]) -> bool:
    return esVacio(interseccion(c1, c2))
 
# 2ª solución
# ===========
 
def disjuntos2(c1: Conj[A], c2: Conj[A]) -> bool:
    if esVacio(c1):
        return True
    mc1 = menor(c1)
    rc1 = elimina(mc1, c1)
    if pertenece(mc1, c2):
        return False
    return disjuntos2(rc1, c2)
 
# 3ª solución
# ===========
 
def disjuntos3(c1: Conj[A], c2: Conj[A]) -> bool:
    xs = conjuntoAlista(c1)
    ys = conjuntoAlista(c2)
    return all((x not in ys for x in xs))
 
# La función conjuntoAlista está definida en el ejercicio
# "Transformaciones entre conjuntos y listas" que se encuentra en
# https://bit.ly/3RexzxH
 
# 4ª solución
# ===========
 
def disjuntos4Aux(c1: Conj[A], c2: Conj[A]) -> bool:
    while not esVacio(c1):
        mc1 = menor(c1)
        if pertenece(mc1, c2):
            return False
        c1 = elimina(mc1, c1)
    return True
 
def disjuntos4(c1: Conj[A], c2: Conj[A]) -> bool:
    _c1 = deepcopy(c1)
    return disjuntos4Aux(_c1, c2)
 
# 5ª solución
# ===========
 
def disjuntos5Aux(c1: Conj[A], c2: Conj[A]) -> bool:
    while not c1.esVacio():
        mc1 = c1.menor()
        if c2.pertenece(mc1):
            return False
        c1.elimina(mc1)
    return True
 
def disjuntos5(c1: Conj[A], c2: Conj[A]) -> bool:
    _c1 = deepcopy(c1)
    return disjuntos5Aux(_c1, c2)
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())
def test_disjuntos(c1: Conj[int], c2: Conj[int]) -> None:
    r = disjuntos(c1, c2)
    assert disjuntos2(c1, c2) == r
    assert disjuntos3(c1, c2) == r
    assert disjuntos4(c1, c2) == r
    assert disjuntos5(c1, c2) == r
 
# La comprobación de las propiedades es
#    > poetry run pytest -q TAD_Conjuntos_disjuntos.py
#    1 passed in 0.34s
Posted in Haskell y Python

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.