Igualdad de conjuntos
Definir la función
|
1 |
iguales :: Ord a => [a] -> [a] -> Bool |
tal que iguales xs ys se verifica si xs e ys son iguales como conjuntos. Por ejemplo,
|
1 2 3 4 |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
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