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 58 59 60 61 62 63 64 65 66 67 68 69 |
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) -- En lo sucesivo, usaremos la 4ª definición subconjunto :: Ord a => [a] -> [a] -> Bool subconjunto = subconjunto4 |
|
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 66 67 68 69 70 71 72 73 74 |
from sys import setrecursionlimit from timeit import Timer, default_timer from typing import TypeVar from hypothesis import given from hypothesis import 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 not xs: return True return xs[0] in ys and subconjunto2(xs[1:], ys) # 3ª solución # =========== def subconjunto3(xs: list[A], ys: list[A]) -> bool: return all(elem in ys for elem 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_filtraAplica(xs: list[int], ys: list[int]) -> None: r = subconjunto1(xs, ys) assert subconjunto2(xs, ys) == r assert subconjunto3(xs, ys) == r assert subconjunto4(xs, ys) == r # La comprobación es # src> poetry run pytest -q Reconocimiento_de_subconjunto.py # 1 passed in 0.31s # 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 # >>> xs = list(range(2*10**4)) # >>> tiempo("subconjunto1(xs, xs)") # 1.15 segundos # >>> tiempo("subconjunto2(xs, xs)") # 2.27 segundos # >>> tiempo("subconjunto3(xs, xs)") # 1.14 segundos # >>> tiempo("subconjunto4(xs, xs)") # 0.00 segundos # En lo sucesivo usaremos la cuarta definición subconjunto = subconjunto4 |