Menu Close

Igualdad de conjuntos

Definir la función

   iguales :: Ord a => [a] -> [a] -> Bool

tal que iguales xs ys se verifica si xs e ys son iguales como conjuntos. Por ejemplo,

   iguales [3,2,3] [2,3]    ==  True
   iguales [3,2,3] [2,3,2]  ==  True
   iguales [3,2,3] [2,3,4]  ==  False
   iguales [2,3] [4,5]      ==  False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

import Data.List (nub, sort)
import Data.Set (fromList)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
iguales1 :: Ord a => [a] -> [a] -> Bool
iguales1 xs ys =
  subconjunto xs ys && subconjunto ys xs
 
-- (subconjunto xs ys) se verifica si xs es un subconjunto de ys. Por
-- ejemplo,
--    subconjunto [3,2,3] [2,5,3,5]  ==  True
--    subconjunto [3,2,3] [2,5,6,5]  ==  False
subconjunto :: Ord a => [a] -> [a] -> Bool
subconjunto xs ys =
  [x | x <- xs, x `elem` ys] == xs
 
-- 2ª solución
-- ===========
 
iguales2 :: Ord a => [a] -> [a] -> Bool
iguales2 xs ys =
  nub (sort xs) == nub (sort ys)
 
-- 3ª solución
-- ===========
 
iguales3 :: Ord a => [a] -> [a] -> Bool
iguales3 xs ys =
  fromList xs == fromList ys
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_iguales :: [Int] -> [Int] -> Bool
prop_iguales xs ys =
  all (== iguales1 xs ys)
      [iguales2 xs ys,
       iguales3 xs ys]
 
-- La comprobación es
--    λ> quickCheck prop_iguales
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> iguales1 [1..2*10^4] [1..2*10^4]
--    True
--    (4.05 secs, 8,553,104 bytes)
--    λ> iguales2 [1..2*10^4] [1..2*10^4]
--    True
--    (4.14 secs, 9,192,768 bytes)
--    λ> iguales3 [1..2*10^4] [1..2*10^4]
--    True
--    (0.01 secs, 8,552,232 bytes)

El código se encuentra en GitHub.


Soluciones en Python

from typing import Any
from timeit import Timer, default_timer
from hypothesis import given, strategies as st
 
# 1ª solución
# ===========
 
def subconjunto(xs: list[Any],
                ys: list[Any]) -> bool:
    return [x for x in xs if x in ys] == xs
 
def iguales1(xs: list[Any],
             ys: list[Any]) -> bool:
    return subconjunto(xs, ys) and subconjunto(ys, xs)
 
# 2ª solución
# ===========
 
def iguales2(xs: list[Any],
             ys: list[Any]) -> bool:
    return set(xs) == set(ys)
 
# Equivalencia de las definiciones
# ================================
 
# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_iguales(xs, ys):
    assert iguales1(xs, ys) == iguales2(xs, ys)
 
# La comprobación es
#    src> poetry run pytest -q igualdad_de_conjuntos.py
#    1 passed in 0.28s
 
# Comparación de eficiencia
# =========================
 
def tiempo(e):
    """Tiempo medio (en segundos) de 10 evaluaciones de la expresión e.
    """
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")
 
# La comparación es
#    >>> xs = list(range(20000))
#    >>> tiempo('iguales1(xs, xs)')
#    2.71 segundos
#    >>> tiempo('iguales2(xs, xs)')
#    0.01 segundos

El código se encuentra en GitHub

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.