Ir al contenido principal

TAD de los conjuntos - Partición de un conjunto según una propiedad

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

   particion :: Ord a => (a -> Bool) -> Conj a -> (Conj a, Conj a)

tal que particion c es el par formado por dos conjuntos: el de los elementos de c que verifican p y el de los elementos que no lo verifican. Por ejemplo,

   λ> ej = inserta 5 (inserta 4 (inserta 7 (inserta 2 vacio)))
   λ> particion even ej
   ({2, 4},{5, 7})

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_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)
import TAD_Subconjunto_por_propiedad (filtra)
import Data.List (partition)
import Test.QuickCheck.HigherOrder

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

particion :: Ord a => (a -> Bool) -> Conj a -> (Conj a, Conj a)
particion p c = (filtra p c, filtra (not . p) c)

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

particion2 :: Ord a => (a -> Bool) -> Conj a -> (Conj a, Conj a)
particion2 p c = (listaAconjunto xs, listaAconjunto ys)
  where
    (xs, ys) = partition p (conjuntoAlista c)

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

-- La propiedad es
prop_particion :: (Int -> Bool) -> [Int] -> Bool
prop_particion p xs =
  particion p c == particion2 p c
  where c = listaAconjunto xs

-- La comprobación es
--    λ> quickCheck' prop_particion
--    +++ OK, passed 100 tests.

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from copy import deepcopy
from typing import Callable, Protocol, TypeVar

from hypothesis import given

from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
                              inserta, menor, vacio)
from src.TAD_Subconjunto_por_propiedad import filtra

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

# 1ª solución
# ===========

def particion(p: Callable[[A], bool],
              c: Conj[A]) -> tuple[Conj[A], Conj[A]]:
    return (filtra(p, c), filtra(lambda x: not p(x), c))

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

def particion2Aux(p: Callable[[A], bool],
                  c: Conj[A]) -> tuple[Conj[A], Conj[A]]:
    r: Conj[A] = vacio()
    s: Conj[A] = vacio()
    while not esVacio(c):
        mc = menor(c)
        c = elimina(mc, c)
        if p(mc):
            r = inserta(mc, r)
        else:
            s = inserta(mc, s)
    return (r, s)

def particion2(p: Callable[[A], bool],
               c: Conj[A]) -> tuple[Conj[A], Conj[A]]:
    _c = deepcopy(c)
    return particion2Aux(p, _c)

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

def particion3Aux(p: Callable[[A], bool],
                  c: Conj[A]) -> tuple[Conj[A], Conj[A]]:
    r: Conj[A] = Conj()
    s: Conj[A] = Conj()
    while not c.esVacio():
        mc = c.menor()
        c.elimina(mc)
        if p(mc):
            r.inserta(mc)
        else:
            s.inserta(mc)
    return (r, s)

def particion3(p: Callable[[A], bool],
               c: Conj[A]) -> tuple[Conj[A], Conj[A]]:
    _c = deepcopy(c)
    return particion3Aux(p, _c)

# Comprobación de equivalencia de las definiciones
# ================================================

# La propiedad es
@given(c=conjuntoAleatorio())
def test_particion(c: Conj[int]) -> None:
    r = particion(lambda x: x % 2 == 0, c)
    assert particion2(lambda x: x % 2 == 0, c) == r
    assert particion3(lambda x: x % 2 == 0, c) == r

# La comprobación es
#    src> poetry run pytest -q TAD_Particion_por_una_propiedad.py
#    1 passed in 0.28s