Ir al contenido principal

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

Se usarán las funciones

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)

-- 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

-- 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))

# 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