{"id":8582,"date":"2024-05-19T13:17:44","date_gmt":"2024-05-19T11:17:44","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8582"},"modified":"2024-05-19T13:17:44","modified_gmt":"2024-05-19T11:17:44","slug":"19-may-24","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/19-may-24\/","title":{"rendered":"Diferencia sim\u00e9trica"},"content":{"rendered":"<p>La <a href=\"http:\/\/bit.ly\/1Rdcqxs\">diferencia sim\u00e9trica<\/a> de dos conjuntos es el conjunto cuyos elementos son aquellos que pertenecen a alguno de los conjuntos iniciales, sin pertenecer a ambos a la vez. Por ejemplo, la diferencia sim\u00e9trica de {2,5,3} y {4,2,3,7} es {5,4,7}.<\/p>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"haskell\">\n   diferenciaSimetrica :: Ord a => [a] -> [a] -> [a]\n<\/pre>\n<p>tal que <code>diferenciaSimetrica xs ys<\/code> es la diferencia sim\u00e9trica de <code>xs<\/code> e <code>ys<\/code>. Por ejemplo,<\/p>\n<pre lang=\"haskell\">\n   diferenciaSimetrica [2,5,3] [4,2,3,7]    ==  [4,5,7]\n   diferenciaSimetrica [2,5,3] [5,2,3]      ==  []\n   diferenciaSimetrica [2,5,2] [4,2,3,7]    ==  [3,4,5,7]\n   diferenciaSimetrica [2,5,2] [4,2,4,7]    ==  [4,5,7]\n   diferenciaSimetrica [2,5,2,4] [4,2,4,7]  ==  [5,7]\n<\/pre>\n<p><!--more--><\/p>\n<h2>1. Soluciones en Haskell<\/h2>\n<pre lang=\"haskell\">\nmodule Diferencia_simetrica where\n\nimport Data.List ((\\\\), intersect, nub, sort, union)\nimport qualified Data.Set as S\nimport Test.Hspec (Spec, describe, hspec, it, shouldBe)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ndiferenciaSimetrica1 :: Ord a => [a] -> [a] -> [a]\ndiferenciaSimetrica1 xs ys =\n  sort (nub ([x | x <- xs, x `notElem` ys] ++\n             [y | y <- ys, y `notElem` xs]))\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ndiferenciaSimetrica2 :: Ord a => [a] -> [a] -> [a]\ndiferenciaSimetrica2 xs ys =\n  sort (nub (filter (`notElem` ys) xs ++\n             filter (`notElem` xs) ys))\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ndiferenciaSimetrica3 :: Ord a => [a] -> [a] -> [a]\ndiferenciaSimetrica3 xs ys =\n  sort (nub (union xs ys \\\\ intersect xs ys))\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\ndiferenciaSimetrica4 :: Ord a => [a] -> [a] -> [a]\ndiferenciaSimetrica4 xs ys =\n  [x | x <- sort (nub (xs ++ ys))\n     , x `notElem` xs || x `notElem` ys]\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\ndiferenciaSimetrica5 :: Ord a => [a] -> [a] -> [a]\ndiferenciaSimetrica5 xs ys =\n  S.elems ((xs' `S.union` ys') `S.difference` (xs' `S.intersection` ys'))\n  where xs' = S.fromList xs\n        ys' = S.fromList ys\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspecG :: ([Int] -> [Int] -> [Int]) -> Spec\nspecG diferenciaSimetrica = do\n  it \"e1\" $\n    diferenciaSimetrica [2,5,3] [4,2,3,7]    `shouldBe`  [4,5,7]\n  it \"e2\" $\n    diferenciaSimetrica [2,5,3] [5,2,3]      `shouldBe`  []\n  it \"e3\" $\n    diferenciaSimetrica [2,5,2] [4,2,3,7]    `shouldBe`  [3,4,5,7]\n  it \"e4\" $\n    diferenciaSimetrica [2,5,2] [4,2,4,7]    `shouldBe`  [4,5,7]\n  it \"e5\" $\n    diferenciaSimetrica [2,5,2,4] [4,2,4,7]  `shouldBe`  [5,7]\n\nspec :: Spec\nspec = do\n  describe \"def. 1\" $ specG diferenciaSimetrica1\n  describe \"def. 2\" $ specG diferenciaSimetrica2\n  describe \"def. 3\" $ specG diferenciaSimetrica3\n  describe \"def. 4\" $ specG diferenciaSimetrica4\n  describe \"def. 5\" $ specG diferenciaSimetrica5\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--    25 examples, 0 failures\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_diferenciaSimetrica :: [Int] -> [Int] -> Bool\nprop_diferenciaSimetrica xs ys =\n  all (== diferenciaSimetrica1 xs ys)\n      [diferenciaSimetrica2 xs ys,\n       diferenciaSimetrica3 xs ys,\n       diferenciaSimetrica4 xs ys,\n       diferenciaSimetrica5 xs ys]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_diferenciaSimetrica\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (diferenciaSimetrica1 [1..2*10^4] [2,4..2*10^4])\n--    10000\n--    (2.34 secs, 10,014,360 bytes)\n--    \u03bb> length (diferenciaSimetrica2 [1..2*10^4] [2,4..2*10^4])\n--    10000\n--    (2.41 secs, 8,174,264 bytes)\n--    \u03bb> length (diferenciaSimetrica3 [1..2*10^4] [2,4..2*10^4])\n--    10000\n--    (5.84 secs, 10,232,006,288 bytes)\n--    \u03bb> length (diferenciaSimetrica4 [1..2*10^4] [2,4..2*10^4])\n--    10000\n--    (5.83 secs, 14,814,184 bytes)\n--    \u03bb> length (diferenciaSimetrica5 [1..2*10^4] [2,4..2*10^4])\n--    10000\n--    (0.02 secs, 7,253,496 bytes)\n<\/pre>\n<h2>2. Soluciones en Python<\/h2>\n<pre lang=\"python\">\nfrom timeit import Timer, default_timer\nfrom typing import TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef diferenciaSimetrica1(xs: list[A], ys: list[A]) -> list[A]:\n    return list(set([x for x in xs if x not in ys] + \\\n                    [y for y in ys if y not in xs]))\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef diferenciaSimetrica2(xs: list[A], ys: list[A]) -> list[A]:\n    return list(set(list(filter(lambda x: x not in ys, xs)) + \\\n                    list(filter(lambda y: y not in xs, ys))))\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef diferenciaSimetrica3(xs: list[A], ys: list[A]) -> list[A]:\n    s1 = set(xs)\n    s2 = set(ys)\n    return list((s1 | s2) - (s1 & s2))\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef diferenciaSimetrica4(xs: list[A], ys: list[A]) -> list[A]:\n    return [x for x in list(set(xs + ys)) if x not in xs or x not in ys]\n\n# 5\u00aa soluci\u00f3n\n# ===========\n\ndef diferenciaSimetrica5(xs: list[A], ys: list[A]) -> list[A]:\n    return list(set(xs) ^ set(ys))\n\n# Verificaci\u00f3n\n# ============\n\ndef test_diferenciaSimetrica() -> None:\n    for diferenciaSimetrica in [diferenciaSimetrica1,\n                                diferenciaSimetrica2,\n                                diferenciaSimetrica3,\n                                diferenciaSimetrica4,\n                                diferenciaSimetrica5]:\n        assert diferenciaSimetrica([2,5,3], [4,2,3,7])    ==  [4,5,7]\n        assert diferenciaSimetrica([2,5,3], [5,2,3])      ==  []\n        assert diferenciaSimetrica([2,5,2], [4,2,3,7])    ==  [3,4,5,7]\n        assert diferenciaSimetrica([2,5,2], [4,2,4,7])    ==  [4,5,7]\n        assert diferenciaSimetrica([2,5,2,4], [4,2,4,7])  ==  [5,7]\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_diferenciaSimetrica()\n#    Verificado\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.lists(st.integers()),\n       st.lists(st.integers()))\ndef test_diferenciaSimetrica_equiv(xs: list[int], ys: list[int]) -> None:\n    assert set(diferenciaSimetrica1(xs, ys)) ==\\\n           set(diferenciaSimetrica2(xs, ys)) ==\\\n           set(diferenciaSimetrica3(xs, ys)) ==\\\n           set(diferenciaSimetrica4(xs, ys)) ==\\\n           set(diferenciaSimetrica5(xs, ys))\n\n# La comprobaci\u00f3n es\n#    >>> test_diferenciaSimetrica_equiv()\n#    >>>\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> tiempo('diferenciaSimetrica1(list(range(1,1+2*10**4)), list(range(2,1+2*10**4,2)))')\n#    1.62 segundos\n#    >>> tiempo('diferenciaSimetrica2(list(range(1,1+2*10**4)), list(range(2,1+2*10**4,2)))')\n#    1.60 segundos\n#    >>> tiempo('diferenciaSimetrica3(list(range(1,1+2*10**4)), list(range(2,1+2*10**4,2)))')\n#    0.02 segundos\n#    >>> tiempo('diferenciaSimetrica4(list(range(1,1+2*10**4)), list(range(2,1+2*10**4,2)))')\n#    2.25 segundos\n#    >>> tiempo('diferenciaSimetrica5(list(range(1,1+2*10**4)), list(range(2,1+2*10**4,2)))')\n#    0.01 segundos\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>La diferencia sim\u00e9trica de dos conjuntos es el conjunto cuyos elementos son aquellos que pertenecen a alguno de los conjuntos iniciales, sin pertenecer a ambos a la vez. Por ejemplo, la diferencia sim\u00e9trica de {2,5,3} y {4,2,3,7} es {5,4,7}. Definir la funci\u00f3n diferenciaSimetrica :: Ord a => [a] -> [a] -> [a] tal que diferenciaSimetrica&#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":"default","_kad_post_title":"default","_kad_post_layout":"default","_kad_post_sidebar_id":"","_kad_post_content_style":"default","_kad_post_vertical_padding":"default","_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":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8582"}],"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=8582"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8582\/revisions"}],"predecessor-version":[{"id":8583,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8582\/revisions\/8583"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8582"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8582"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8582"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}