{"id":6844,"date":"2022-03-29T06:00:07","date_gmt":"2022-03-29T04:00:07","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6844"},"modified":"2022-04-05T08:26:34","modified_gmt":"2022-04-05T06:26:34","slug":"diferencia-simetrica","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/diferencia-simetrica\/","title":{"rendered":"Diferencia sim\u00e9trica"},"content":{"rendered":"

La 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

Definir la funci\u00f3n<\/p>\n

\n   diferenciaSimetrica :: Ord a => [a] -> [a] -> [a]\n<\/pre>\n
tal que (diferenciaSimetrica xs ys)<\/code> es la diferencia sim\u00e9trica de xs<\/code> e ys<\/code>. Por ejemplo,<\/p>\n
\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
Soluciones<\/h4>\n
\nimport Test.QuickCheck\nimport Data.List ((\\\\), intersect, nub, sort, union)\nimport qualified Data.Set as S\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] ++ [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 ++ 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-- 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
El c\u00f3digo se encuentra en GitHub<\/a>.<\/p>\n
La elaboraci\u00f3n de las soluciones se describe en el siguiente v\u00eddeo<\/p>\n