Reconocimiento de subconjunto
Definir la función
|
1 |
subconjunto :: Ord a => [a] -> [a] -> Bool |
tal que subconjunto xs ys se verifica si xs es un subconjunto de ys. por ejemplo,
|
1 2 |
subconjunto [3,2,3] [2,5,3,5] == True subconjunto [3,2,3] [2,5,6,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 |
module Reconocimiento_de_subconjunto where import Data.List (nub, sort) import Data.Set (fromList, isSubsetOf) import Test.QuickCheck -- 1ª solución subconjunto1 :: Ord a => [a] -> [a] -> Bool subconjunto1 xs ys = [x | x <- xs, x `elem` ys] == xs -- 2ª solución subconjunto2 :: Ord a => [a] -> [a] -> Bool subconjunto2 [] _ = True subconjunto2 (x:xs) ys = x `elem` ys && subconjunto2 xs ys -- 3ª solución subconjunto3 :: Ord a => [a] -> [a] -> Bool subconjunto3 xs ys = all (`elem` ys) xs -- 4ª solución subconjunto4 :: Ord a => [a] -> [a] -> Bool subconjunto4 xs ys = fromList xs `isSubsetOf` fromList ys -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_subconjunto :: [Int] -> [Int] -> Bool prop_subconjunto xs ys = all (== subconjunto1 xs ys) [subconjunto2 xs ys, subconjunto3 xs ys, subconjunto4 xs ys] -- La comprobación es -- λ> quickCheck prop_subconjunto -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> subconjunto1 [1..2*10^4] [1..2*10^4] -- True -- (1.81 secs, 5,992,448 bytes) -- λ> subconjunto2 [1..2*10^4] [1..2*10^4] -- True -- (1.83 secs, 6,952,200 bytes) -- λ> subconjunto3 [1..2*10^4] [1..2*10^4] -- True -- (1.75 secs, 4,712,304 bytes) -- λ> subconjunto4 [1..2*10^4] [1..2*10^4] -- True -- (0.04 secs, 6,312,056 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 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
from typing import TypeVar from timeit import Timer, default_timer from sys import setrecursionlimit from hypothesis import given, strategies as st setrecursionlimit(10**6) A = TypeVar('A') # 1ª solución def subconjunto1(xs: list[A], ys: list[A]) -> bool: return [x for x in xs if x in ys] == xs # 2ª solución def subconjunto2(xs: list[A], ys: list[A]) -> bool: if xs: return xs[0] in ys and subconjunto2(xs[1:], ys) return True # 3ª solución def subconjunto3(xs: list[A], ys: list[A]) -> bool: return all(x in ys for x in xs) # 4ª solución def subconjunto4(xs: list[A], ys: list[A]) -> bool: return set(xs) <= set(ys) # Comprobación de equivalencia # ============================ # La propiedad es @given(st.lists(st.integers()), st.lists(st.integers())) def test_subconjunto(xs, ys): assert subconjunto1(xs, ys)\ == subconjunto2(xs, ys)\ == subconjunto3(xs, ys)\ == subconjunto4(xs, ys) # La comprobación es # src> poetry run pytest -q reconocimiento_de_subconjunto.py # 1 passed in 0.34s # Comparación de eficiencia # ========================= def tiempo(e): """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 # >>> xs = list(range(20000)) # >>> tiempo('subconjunto1(xs, xs)') # 1.27 segundos # >>> tiempo('subconjunto2(xs, xs)') # 1.84 segundos # >>> tiempo('subconjunto3(xs, xs)') # 1.19 segundos # >>> tiempo('subconjunto4(xs, xs)') # 0.01 segundos |
El código se encuentra en GitHub.
Comentarios
- La expresión «x pertenece a ys» se escribe
- en Haskell, como x `elem` ys
- en Python, como x in ys
- La expresión «todos los elementos de xs verifican la propiedad p» se escribe
- en Haskell, como all p xs
- en Python, como all(p(x) for x in xs)
- Si xs e ys son conjuntos, la expresión «xs es subconjunto de ys» se escribe
- en Haskell, como xs `isSubsetOf` ys
- en Python, como xs <= ys