{"id":7958,"date":"2023-03-21T06:00:32","date_gmt":"2023-03-21T04:00:32","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7958"},"modified":"2023-02-22T20:42:33","modified_gmt":"2023-02-22T18:42:33","slug":"21-mar-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/21-mar-23\/","title":{"rendered":"TAD de los conjuntos: Partici\u00f3n seg\u00fan un n\u00famero"},"content":{"rendered":"<p>Utilizando el <a href=\"https:\/\/bit.ly\/3HbB7fo\">tipo abstracto de datos de los conjuntos<\/a> definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   divide :: (Ord a) => a-> Conj a -> (Conj a, Conj a)\n<\/pre>\n<p>tal que <code>divide x c<\/code> es el par formado por dos subconjuntos de <code>c<\/code>: el de los elementos menores o iguales que <code>x<\/code> y el de los mayores que <code>x<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> divide 5 (inserta 7 (inserta 2 (inserta 8 vacio)))\n   ({2},{7, 8})\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport TAD.Conjunto (Conj, vacio, inserta, esVacio, menor, elimina)\nimport TAD_Particion_por_una_propiedad (particion)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ndivide :: Ord a => a-> Conj a -> (Conj a, Conj a)\ndivide x c\n  | esVacio c = (vacio, vacio)\n  | mc <= x   = (inserta mc c1, c2)\n  | otherwise = (c1, inserta mc c2)\n  where\n    mc       = menor c\n    rc       = elimina mc c\n    (c1, c2) = divide x rc\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ndivide2 :: Ord a => a-> Conj a -> (Conj a, Conj a)\ndivide2 x = particion (<= x)\n\n-- La funci\u00f3n particion est\u00e1 definida en el ejercicio\n-- \"Partici\u00f3n de un conjunto seg\u00fan una propiedad\" que se encuentra en\n-- https:\/\/bit.ly\/3YCOah5\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_divide :: Int -> Conj Int -> Bool\nprop_divide x c =\n  divide x c == divide2 x c\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_divide\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom __future__ import annotations\n\nfrom abc import abstractmethod\nfrom copy import deepcopy\nfrom typing import Protocol, TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nfrom src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,\n                              inserta, menor, vacio)\nfrom src.TAD_Particion_por_una_propiedad import particion\n\nclass Comparable(Protocol):\n    @abstractmethod\n    def __lt__(self: A, otro: A) -> bool:\n        pass\n\nA = TypeVar('A', bound=Comparable)\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef divide(x: A, c: Conj[A]) -> tuple[Conj[A], Conj[A]]:\n    if esVacio(c):\n        return (vacio(), vacio())\n    mc = menor(c)\n    rc = elimina(mc, c)\n    (c1, c2) = divide(x, rc)\n    if mc <= x:\n        return (inserta(mc, c1), c2)\n    return (c1, inserta(mc, c2))\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef divide2(x: A, c: Conj[A]) -> tuple[Conj[A], Conj[A]]:\n    return particion(lambda y: y <= x, c)\n\n# La funci\u00f3n particion est\u00e1 definida en el ejercicio\n# \"Partici\u00f3n de un conjunto seg\u00fan una propiedad\" que se encuentra en\n# https:\/\/bit.ly\/3YCOah5\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef divide3Aux(x: A, c: Conj[A]) -> tuple[Conj[A], Conj[A]]:\n    r: Conj[A] = vacio()\n    s: Conj[A] = vacio()\n    while not esVacio(c):\n        mc = menor(c)\n        c = elimina(mc, c)\n        if mc <= x:\n            r = inserta(mc, r)\n        else:\n            s = inserta(mc, s)\n    return (r, s)\n\ndef divide3(x: A, c: Conj[A]) -> tuple[Conj[A], Conj[A]]:\n    _c = deepcopy(c)\n    return divide3Aux(x, _c)\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef divide4Aux(x: A, c: Conj[A]) -> tuple[Conj[A], Conj[A]]:\n    r: Conj[A] = Conj()\n    s: Conj[A] = Conj()\n    while not c.esVacio():\n        mc = c.menor()\n        c.elimina(mc)\n        if mc <= x:\n            r.inserta(mc)\n        else:\n            s.inserta(mc)\n    return (r, s)\n\ndef divide4(x: A, c: Conj[A]) -> tuple[Conj[A], Conj[A]]:\n    _c = deepcopy(c)\n    return divide4Aux(x, _c)\n\n# Comprobaci\u00f3n de equivalencia de las definiciones\n# ================================================\n\n# La propiedad es\n@given(x=st.integers(), c=conjuntoAleatorio())\ndef test_particion(x: int, c: Conj[int]) -> None:\n    r = divide(x, c)\n    assert divide2(x, c) == r\n    assert divide3(x, c) == r\n    assert divide4(x, c) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q TAD_Particion_segun_un_numero.py\n#    1 passed in 0.30s\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Utilizando el tipo abstracto de datos de los conjuntos definir la funci\u00f3n divide :: (Ord a) => a-> Conj a -> (Conj a, Conj a) tal que divide x c es el par formado por dos subconjuntos de c: el de los elementos menores o iguales que x y el de los mayores que x&#8230;.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[581],"tags":[331,585],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7958"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=7958"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7958\/revisions"}],"predecessor-version":[{"id":7985,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7958\/revisions\/7985"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7958"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7958"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7958"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}