Ir al contenido principal

TAD de los conjuntos - Diferencia simétrica

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

   diferenciaSimetrica :: Ord a => Conj a -> Conj a -> Conj a

tal que diferenciaSimetrica c1 c2 es la diferencia simétrica de los conjuntos c1 y c2. Por ejemplo,

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

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)
import TAD_Diferencia_de_conjuntos (diferencia)
import TAD_Interseccion_de_dos_conjuntos (interseccion)
import TAD_Union_de_dos_conjuntos (union)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)

import Test.QuickCheck

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

diferenciaSimetrica :: Ord a => Conj a -> Conj a -> Conj a
diferenciaSimetrica c1 c2 =
  diferencia (union c1 c2) (interseccion c1 c2)

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

diferenciaSimetrica2 :: Ord a => Conj a -> Conj a -> Conj a
diferenciaSimetrica2 c1 c2 =
  listaAconjunto ([x | x <- xs, x `notElem` ys] ++
                  [y | y <- ys, y `notElem` xs])
  where xs = conjuntoAlista c1
        ys = conjuntoAlista c2

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

-- La propiedad es
prop_diferenciaSimetrica :: Conj Int -> Conj Int -> Bool
prop_diferenciaSimetrica c1 c2 =
  diferenciaSimetrica c1 c2 == diferenciaSimetrica2 c2 c1

-- La comprobación es
--    λ> quickCheck prop_diferenciaSimetrica
--    +++ 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_Diferencia_de_conjuntos import diferencia
from src.TAD_Interseccion_de_dos_conjuntos import interseccion
from src.TAD_Transformaciones_conjuntos_listas import (conjuntoAlista,
                                                       listaAconjunto)
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 diferenciaSimetrica(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    return diferencia(union(c1, c2), interseccion(c1, c2))

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

def diferenciaSimetrica2(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    xs = conjuntoAlista(c1)
    ys = conjuntoAlista(c2)
    return listaAconjunto([x for x in xs if x not in ys] +
                          [y for y in ys if y not in xs])

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

def diferenciaSimetrica3(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    r: Conj[A] = vacio()
    _c1 = deepcopy(c1)
    _c2 = deepcopy(c2)
    while not esVacio(_c1):
        mc1 = menor(_c1)
        if not pertenece(mc1, c2):
            r = inserta(mc1, r)
        _c1 = elimina(mc1, _c1)
    while not esVacio(_c2):
        mc2 = menor(_c2)
        if not pertenece(mc2, c1):
            r = inserta(mc2, r)
        _c2 = elimina(mc2, _c2)
    return r

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

# La propiedad es
@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())
def test_diferenciaSimetrica(c1: Conj[int], c2: Conj[int]) -> None:
    r = diferenciaSimetrica(c1, c2)
    assert diferenciaSimetrica2(c1, c2) == r
    assert diferenciaSimetrica3(c1, c2) == r

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