Producto cartesiano de dos conjuntos
Definir la función
|
1 |
producto :: [a] -> [b] -> [(a,b)] |
tal que producto xs ys es el producto cartesiano de xs e ys. Por
ejemplo,
|
1 |
producto [1,3] [2,4] == [(1,2),(1,4),(3,2),(3,4)] |
Comprobar con QuickCheck que el número de elementos de producto xs y es el producto del número de elementos de xs y de ys.
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 |
import Test.QuickCheck -- 1ª solución -- =========== producto1 :: [a] -> [a] -> [(a,a)] producto1 xs ys = [(x,y) | x <- xs, y <- ys] -- 2ª solución -- =========== producto2 :: [a] -> [a] -> [(a,a)] producto2 [] _ = [] producto2 (x:xs) ys = [(x,y) | y <- ys] ++ producto2 xs ys -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_producto :: [Int] -> [Int] -> Bool prop_producto xs ys = producto1 xs ys `iguales` producto2 xs ys -- (iguales xs ys) se verifica si xs e ys son iguales. 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 iguales :: Ord a => [a] -> [a] -> Bool iguales 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 -- La comprobación es -- λ> quickCheck prop_producto -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (producto1 [1..4000] [1..4000]) -- 16000000 -- (2.33 secs, 1,537,551,208 bytes) -- λ> length (producto2 [1..4000] [1..4000]) -- 16000000 -- (2.87 secs, 2,434,095,160 bytes) -- Comprobación de la propiedad -- ============================ -- La propiedad es prop_elementos_producto :: [Int] -> [Int] -> Bool prop_elementos_producto xs ys = length (producto1 xs ys) == length xs * length ys -- La comprobación es -- λ> quickCheck prop_elementos_producto -- +++ OK, passed 100 tests. |
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 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') B = TypeVar('B') # 1ª solución # =========== def producto1(xs: list[A], ys: list[B]) -> list[tuple[A, B]]: return [(x, y) for x in xs for y in ys] # 2ª solución # =========== def producto2(xs: list[A], ys: list[B]) -> list[tuple[A, B]]: if xs: return [(xs[0], y) for y in ys] + producto2(xs[1:], ys) return [] # Comprobación de equivalencia # ============================ # La propiedad es @given(st.lists(st.integers()), st.lists(st.integers())) def test_producto(xs: list[int], ys: list[int]) -> None: assert sorted(producto1(xs, ys)) == sorted(producto2(xs, ys)) # La comprobación es # src> poetry run pytest -q producto_cartesiano_de_dos_conjuntos.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 # >>> tiempo('len(producto1(range(0, 1000), range(0, 500)))') # 0.03 segundos # >>> tiempo('len(producto2(range(0, 1000), range(0, 500)))') # 2.58 segundos # Comprobación de la propiedad # ============================ # La propiedad es @given(st.lists(st.integers()), st.lists(st.integers())) def test_elementos_producto(xs: list[int], ys: list[int]) -> None: assert len(producto1(xs, ys)) == len(xs) * len(ys) # La comprobación es # src> poetry run pytest -q producto_cartesiano_de_dos_conjuntos.py # 2 passed in 0.48s |
El código se encuentra en GitHub.