Menu Close

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

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)
 
-- La función filtra está definida en el ejercicio
-- "Subconjunto determinado por una propiedad" que se encuentra en
-- https://bit.ly/3lplFoV
 
-- 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))
 
# La función filtra está definida en el ejercicio
# "Subconjunto determinado por una propiedad" que se encuentra en
# https://bit.ly/3lplFoV
 
# 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
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.