Diferencia simétrica

La diferencia simétrica 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étrica de {2,5,3} y {4,2,3,7} es {5,4,7}.

Definir la función

   diferenciaSimetrica :: Ord a => [a] -> [a] -> [a]

1	diferenciaSimetrica :: Ord a => [a] -> [a] -> [a]

tal que diferenciaSimetrica xs ys es la diferencia simétrica de xs e ys. Por ejemplo,

   diferenciaSimetrica [2,5,3] [4,2,3,7]    ==  [4,5,7]
   diferenciaSimetrica [2,5,3] [5,2,3]      ==  []
   diferenciaSimetrica [2,5,2] [4,2,3,7]    ==  [3,4,5,7]
   diferenciaSimetrica [2,5,2] [4,2,4,7]    ==  [4,5,7]
   diferenciaSimetrica [2,5,2,4] [4,2,4,7]  ==  [5,7]

diferenciaSimetrica [2,5,3] [4,2,3,7] == [4,5,7]

diferenciaSimetrica [2,5,3] [5,2,3] == []

diferenciaSimetrica [2,5,2] [4,2,3,7] == [3,4,5,7]

diferenciaSimetrica [2,5,2] [4,2,4,7] == [4,5,7]

diferenciaSimetrica [2,5,2,4] [4,2,4,7] == [5,7]

1. Soluciones en Haskell

module Diferencia_simetrica where

import Data.List ((\\), intersect, nub, sort, union)
import qualified Data.Set as S
import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

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

diferenciaSimetrica1 :: Ord a => [a] -> [a] -> [a]
diferenciaSimetrica1 xs ys =
  sort (nub ([x | x <- xs, x `notElem` ys] ++
             [y | y <- ys, y `notElem` xs]))

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

diferenciaSimetrica2 :: Ord a => [a] -> [a] -> [a]
diferenciaSimetrica2 xs ys =
  sort (nub (filter (`notElem` ys) xs ++
             filter (`notElem` xs) ys))

-- 3ª solución
-- ===========

diferenciaSimetrica3 :: Ord a => [a] -> [a] -> [a]
diferenciaSimetrica3 xs ys =
  sort (nub (union xs ys \\ intersect xs ys))

-- 4ª solución
-- ===========

diferenciaSimetrica4 :: Ord a => [a] -> [a] -> [a]
diferenciaSimetrica4 xs ys =
  [x | x <- sort (nub (xs ++ ys))
     , x `notElem` xs || x `notElem` ys]

-- 5ª solución
-- ===========

diferenciaSimetrica5 :: Ord a => [a] -> [a] -> [a]
diferenciaSimetrica5 xs ys =
  S.elems ((xs' `S.union` ys') `S.difference` (xs' `S.intersection` ys'))
  where xs' = S.fromList xs
        ys' = S.fromList ys

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: ([Int] -> [Int] -> [Int]) -> Spec
specG diferenciaSimetrica = do
  it "e1" $
    diferenciaSimetrica [2,5,3] [4,2,3,7]    `shouldBe`  [4,5,7]
  it "e2" $
    diferenciaSimetrica [2,5,3] [5,2,3]      `shouldBe`  []
  it "e3" $
    diferenciaSimetrica [2,5,2] [4,2,3,7]    `shouldBe`  [3,4,5,7]
  it "e4" $
    diferenciaSimetrica [2,5,2] [4,2,4,7]    `shouldBe`  [4,5,7]
  it "e5" $
    diferenciaSimetrica [2,5,2,4] [4,2,4,7]  `shouldBe`  [5,7]

spec :: Spec
spec = do
  describe "def. 1" $ specG diferenciaSimetrica1
  describe "def. 2" $ specG diferenciaSimetrica2
  describe "def. 3" $ specG diferenciaSimetrica3
  describe "def. 4" $ specG diferenciaSimetrica4
  describe "def. 5" $ specG diferenciaSimetrica5

-- La verificación es
--    λ> verifica
--    25 examples, 0 failures

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

-- La propiedad es
prop_diferenciaSimetrica :: [Int] -> [Int] -> Bool
prop_diferenciaSimetrica xs ys =
  all (== diferenciaSimetrica1 xs ys)
      [diferenciaSimetrica2 xs ys,
       diferenciaSimetrica3 xs ys,
       diferenciaSimetrica4 xs ys,
       diferenciaSimetrica5 xs ys]

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

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> length (diferenciaSimetrica1 [1..2*10^4] [2,4..2*10^4])
--    10000
--    (2.34 secs, 10,014,360 bytes)
--    λ> length (diferenciaSimetrica2 [1..2*10^4] [2,4..2*10^4])
--    10000
--    (2.41 secs, 8,174,264 bytes)
--    λ> length (diferenciaSimetrica3 [1..2*10^4] [2,4..2*10^4])
--    10000
--    (5.84 secs, 10,232,006,288 bytes)
--    λ> length (diferenciaSimetrica4 [1..2*10^4] [2,4..2*10^4])
--    10000
--    (5.83 secs, 14,814,184 bytes)
--    λ> length (diferenciaSimetrica5 [1..2*10^4] [2,4..2*10^4])
--    10000
--    (0.02 secs, 7,253,496 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

module Diferencia_simetrica where

import Data.List ((\\), intersect, nub, sort, union)

import qualified Data.Set as S

import Test.Hspec (Spec, describe, hspec, it, shouldBe)

import Test.QuickCheck

-- 1ª solución

-- ===========

diferenciaSimetrica1 :: Ord a => [a] -> [a] -> [a]

diferenciaSimetrica1 xs ys =

sort (nub ([x | x <- xs, x `notElem` ys] ++

[y | y <- ys, y `notElem` xs]))

-- 2ª solución

-- ===========

diferenciaSimetrica2 :: Ord a => [a] -> [a] -> [a]

diferenciaSimetrica2 xs ys =

sort (nub (filter (`notElem` ys) xs ++

filter (`notElem` xs) ys))

-- 3ª solución

-- ===========

diferenciaSimetrica3 :: Ord a => [a] -> [a] -> [a]

diferenciaSimetrica3 xs ys =

sort (nub (union xs ys \\ intersect xs ys))

-- 4ª solución

-- ===========

diferenciaSimetrica4 :: Ord a => [a] -> [a] -> [a]

diferenciaSimetrica4 xs ys =

[x | x <- sort (nub (xs ++ ys))

, x `notElem` xs || x `notElem` ys]

-- 5ª solución

-- ===========

diferenciaSimetrica5 :: Ord a => [a] -> [a] -> [a]

diferenciaSimetrica5 xs ys =

S.elems ((xs' `S.union` ys') `S.difference` (xs' `S.intersection` ys'))

where xs' = S.fromList xs

ys' = S.fromList ys

-- Verificación

-- ============

verifica :: IO ()

verifica = hspec spec

specG :: ([Int] -> [Int] -> [Int]) -> Spec

specG diferenciaSimetrica = do

it "e1" $

diferenciaSimetrica [2,5,3] [4,2,3,7] `shouldBe` [4,5,7]

it "e2" $

diferenciaSimetrica [2,5,3] [5,2,3] `shouldBe` []

it "e3" $

diferenciaSimetrica [2,5,2] [4,2,3,7] `shouldBe` [3,4,5,7]

it "e4" $

diferenciaSimetrica [2,5,2] [4,2,4,7] `shouldBe` [4,5,7]

it "e5" $

diferenciaSimetrica [2,5,2,4] [4,2,4,7] `shouldBe` [5,7]

spec :: Spec

spec = do

describe "def. 1" $ specG diferenciaSimetrica1

describe "def. 2" $ specG diferenciaSimetrica2

describe "def. 3" $ specG diferenciaSimetrica3

describe "def. 4" $ specG diferenciaSimetrica4

describe "def. 5" $ specG diferenciaSimetrica5

-- La verificación es

-- λ> verifica

-- 25 examples, 0 failures

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_diferenciaSimetrica :: [Int] -> [Int] -> Bool

prop_diferenciaSimetrica xs ys =

all (== diferenciaSimetrica1 xs ys)

[diferenciaSimetrica2 xs ys,

diferenciaSimetrica3 xs ys,

diferenciaSimetrica4 xs ys,

diferenciaSimetrica5 xs ys]

-- La comprobación es

-- λ> quickCheck prop_diferenciaSimetrica

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> length (diferenciaSimetrica1 [1..2*10^4] [2,4..2*10^4])

-- 10000

-- (2.34 secs, 10,014,360 bytes)

-- λ> length (diferenciaSimetrica2 [1..2*10^4] [2,4..2*10^4])

-- 10000

-- (2.41 secs, 8,174,264 bytes)

-- λ> length (diferenciaSimetrica3 [1..2*10^4] [2,4..2*10^4])

-- 10000

-- (5.84 secs, 10,232,006,288 bytes)

-- λ> length (diferenciaSimetrica4 [1..2*10^4] [2,4..2*10^4])

-- 10000

-- (5.83 secs, 14,814,184 bytes)

-- λ> length (diferenciaSimetrica5 [1..2*10^4] [2,4..2*10^4])

-- 10000

-- (0.02 secs, 7,253,496 bytes)

2. Soluciones en Python

from timeit import Timer, default_timer
from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st

A = TypeVar('A')

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

def diferenciaSimetrica1(xs: list[A], ys: list[A]) -> list[A]:
    return list(set([x for x in xs if x not in ys] + \
                    [y for y in ys if y not in xs]))

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

def diferenciaSimetrica2(xs: list[A], ys: list[A]) -> list[A]:
    return list(set(list(filter(lambda x: x not in ys, xs)) + \
                    list(filter(lambda y: y not in xs, ys))))

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

def diferenciaSimetrica3(xs: list[A], ys: list[A]) -> list[A]:
    s1 = set(xs)
    s2 = set(ys)
    return list((s1 | s2) - (s1 & s2))

# 4ª solución
# ===========

def diferenciaSimetrica4(xs: list[A], ys: list[A]) -> list[A]:
    return [x for x in list(set(xs + ys)) if x not in xs or x not in ys]

# 5ª solución
# ===========

def diferenciaSimetrica5(xs: list[A], ys: list[A]) -> list[A]:
    return list(set(xs) ^ set(ys))

# Verificación
# ============

def test_diferenciaSimetrica() -> None:
    for diferenciaSimetrica in [diferenciaSimetrica1,
                                diferenciaSimetrica2,
                                diferenciaSimetrica3,
                                diferenciaSimetrica4,
                                diferenciaSimetrica5]:
        assert diferenciaSimetrica([2,5,3], [4,2,3,7])    ==  [4,5,7]
        assert diferenciaSimetrica([2,5,3], [5,2,3])      ==  []
        assert diferenciaSimetrica([2,5,2], [4,2,3,7])    ==  [3,4,5,7]
        assert diferenciaSimetrica([2,5,2], [4,2,4,7])    ==  [4,5,7]
        assert diferenciaSimetrica([2,5,2,4], [4,2,4,7])  ==  [5,7]
    print("Verificado")

# La verificación es
#    >>> test_diferenciaSimetrica()
#    Verificado

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_diferenciaSimetrica_equiv(xs: list[int], ys: list[int]) -> None:
    assert set(diferenciaSimetrica1(xs, ys)) ==\
           set(diferenciaSimetrica2(xs, ys)) ==\
           set(diferenciaSimetrica3(xs, ys)) ==\
           set(diferenciaSimetrica4(xs, ys)) ==\
           set(diferenciaSimetrica5(xs, ys))

# La comprobación es
#    >>> test_diferenciaSimetrica_equiv()
#    >>>

# Comparación de eficiencia
# =========================


def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('diferenciaSimetrica1(list(range(1,1+2*10**4)), list(range(2,1+2*10**4,2)))')
#    1.62 segundos
#    >>> tiempo('diferenciaSimetrica2(list(range(1,1+2*10**4)), list(range(2,1+2*10**4,2)))')
#    1.60 segundos
#    >>> tiempo('diferenciaSimetrica3(list(range(1,1+2*10**4)), list(range(2,1+2*10**4,2)))')
#    0.02 segundos
#    >>> tiempo('diferenciaSimetrica4(list(range(1,1+2*10**4)), list(range(2,1+2*10**4,2)))')
#    2.25 segundos
#    >>> tiempo('diferenciaSimetrica5(list(range(1,1+2*10**4)), list(range(2,1+2*10**4,2)))')
#    0.01 segundos

from timeit import Timer, default_timer

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

A = TypeVar('A')

# 1ª solución

# ===========

def diferenciaSimetrica1(xs: list[A], ys: list[A]) -> list[A]:

return list(set([x for x in xs if x not in ys] + \

[y for y in ys if y not in xs]))

# 2ª solución

# ===========

def diferenciaSimetrica2(xs: list[A], ys: list[A]) -> list[A]:

return list(set(list(filter(lambda x: x not in ys, xs)) + \

list(filter(lambda y: y not in xs, ys))))

# 3ª solución

# ===========

def diferenciaSimetrica3(xs: list[A], ys: list[A]) -> list[A]:

s1 = set(xs)

s2 = set(ys)

return list((s1 | s2) - (s1 & s2))

# 4ª solución

# ===========

def diferenciaSimetrica4(xs: list[A], ys: list[A]) -> list[A]:

return [x for x in list(set(xs + ys)) if x not in xs or x not in ys]

# 5ª solución

# ===========

def diferenciaSimetrica5(xs: list[A], ys: list[A]) -> list[A]:

return list(set(xs) ^ set(ys))

# Verificación

# ============

def test_diferenciaSimetrica() -> None:

for diferenciaSimetrica in [diferenciaSimetrica1,

diferenciaSimetrica2,

diferenciaSimetrica3,

diferenciaSimetrica4,

diferenciaSimetrica5]:

assert diferenciaSimetrica([2,5,3], [4,2,3,7]) == [4,5,7]

assert diferenciaSimetrica([2,5,3], [5,2,3]) == []

assert diferenciaSimetrica([2,5,2], [4,2,3,7]) == [3,4,5,7]

assert diferenciaSimetrica([2,5,2], [4,2,4,7]) == [4,5,7]

assert diferenciaSimetrica([2,5,2,4], [4,2,4,7]) == [5,7]

print("Verificado")

# La verificación es

# >>> test_diferenciaSimetrica()

# Verificado

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.lists(st.integers()),

st.lists(st.integers()))

def test_diferenciaSimetrica_equiv(xs: list[int], ys: list[int]) -> None:

assert set(diferenciaSimetrica1(xs, ys)) ==\

set(diferenciaSimetrica2(xs, ys)) ==\

set(diferenciaSimetrica3(xs, ys)) ==\

set(diferenciaSimetrica4(xs, ys)) ==\

set(diferenciaSimetrica5(xs, ys))

# La comprobación es

# >>> test_diferenciaSimetrica_equiv()

# >>>

# Comparación de eficiencia

# =========================

def tiempo(e: str) -> None:

"""Tiempo (en segundos) de evaluar la expresión e."""

t = Timer(e, "", default_timer, globals()).timeit(1)

print(f"{t:0.2f} segundos")

# La comparación es

# >>> tiempo('diferenciaSimetrica1(list(range(1,1+2*10**4)), list(range(2,1+2*10**4,2)))')

# 1.62 segundos

# >>> tiempo('diferenciaSimetrica2(list(range(1,1+2*10**4)), list(range(2,1+2*10**4,2)))')

# 1.60 segundos

# >>> tiempo('diferenciaSimetrica3(list(range(1,1+2*10**4)), list(range(2,1+2*10**4,2)))')

# 0.02 segundos

# >>> tiempo('diferenciaSimetrica4(list(range(1,1+2*10**4)), list(range(2,1+2*10**4,2)))')

# 2.25 segundos

# >>> tiempo('diferenciaSimetrica5(list(range(1,1+2*10**4)), list(range(2,1+2*10**4,2)))')

# 0.01 segundos

Diferencia simétrica

1. Soluciones en Haskell

2. Soluciones en Python

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

1. Soluciones en Haskell

2. Soluciones en Python

Se puede imprimir o compartir con

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico