Subconjuntos de un conjunto
Definir la función
|
1 |
subconjuntos :: [a] -> [[a]] |
tal que subconjuntos xs es la lista de las subconjuntos de la lista xs. Por ejemplo,
|
1 2 3 4 5 |
λ> subconjuntos [2,3,4] [[2,3,4],[2,3],[2,4],[2],[3,4],[3],[4],[]] λ> subconjuntos [1,2,3,4] [[1,2,3,4],[1,2,3],[1,2,4],[1,2],[1,3,4],[1,3],[1,4],[1], [2,3,4], [2,3], [2,4], [2], [3,4], [3], [4], []] |
Comprobar con QuickChek que el número de elementos de subconjuntos xs es 2 elevado al número de elementos de xs.
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 |
import Data.List (sort, subsequences) import Test.QuickCheck -- 1ª solución -- =========== subconjuntos1 :: [a] -> [[a]] subconjuntos1 [] = [[]] subconjuntos1 (x:xs) = [x:ys | ys <- sub] ++ sub where sub = subconjuntos1 xs -- 2ª solución -- =========== subconjuntos2 :: [a] -> [[a]] subconjuntos2 [] = [[]] subconjuntos2 (x:xs) = map (x:) sub ++ sub where sub = subconjuntos2 xs -- 3ª solución -- =========== subconjuntos3 :: [a] -> [[a]] subconjuntos3 = subsequences -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_subconjuntos :: [Int] -> Bool prop_subconjuntos xs = all (== sort (subconjuntos1 xs)) [sort (subconjuntos2 xs), sort (subconjuntos3 xs)] -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=7}) prop_subconjuntos -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (subconjuntos1 [1..23]) -- 8388608 -- (2.05 secs, 1,476,991,840 bytes) -- λ> length (subconjuntos2 [1..23]) -- 8388608 -- (0.87 secs, 1,208,555,312 bytes) -- λ> length (subconjuntos3 [1..23]) -- 8388608 -- (0.09 secs, 873,006,608 bytes) -- Comprobación de la propiedad -- ============================ -- La propiedad es prop_length_subconjuntos :: [Int] -> Bool prop_length_subconjuntos xs = length (subconjuntos1 xs) == 2 ^ length xs -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=7}) prop_length_subconjuntos -- +++ OK, passed 100 tests. |
|
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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
from itertools import combinations from sys import setrecursionlimit from timeit import Timer, default_timer from typing import TypeVar from hypothesis import given from hypothesis import strategies as st from sympy import FiniteSet setrecursionlimit(10**6) A = TypeVar('A') # 1ª solución # =========== def subconjuntos1(xs: list[A]) -> list[list[A]]: if xs: sub = subconjuntos1(xs[1:]) return [[xs[0]] + ys for ys in sub] + sub return [[]] # 2ª solución # =========== def subconjuntos2(xs: list[A]) -> list[list[A]]: if xs: sub = subconjuntos1(xs[1:]) return list(map((lambda ys: [xs[0]] + ys), sub)) + sub return [[]] # 3ª solución # =========== def subconjuntos3(xs: list[A]) -> list[list[A]]: c = FiniteSet(*xs) return list(map(list, c.powerset())) # 4ª solución # =========== def subconjuntos4(xs: list[A]) -> list[list[A]]: return [list(ys) for r in range(len(xs)+1) for ys in combinations(xs, r)] # Comprobación de equivalencia # ============================ # La propiedad es @given(st.lists(st.integers(), max_size=5)) def test_subconjuntos(xs: list[int]) -> None: ys = list(set(xs)) r = sorted([sorted(zs) for zs in subconjuntos1(ys)]) assert sorted([sorted(zs) for zs in subconjuntos2(ys)]) == r assert sorted([sorted(zs) for zs in subconjuntos3(ys)]) == r assert sorted([sorted(zs) for zs in subconjuntos4(ys)]) == r # La comprobación es # src> poetry run pytest -q subconjuntos_de_un_conjunto.py # 1 passed in 0.89s # 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('subconjuntos1(range(14))') # 0.00 segundos # >>> tiempo('subconjuntos2(range(14))') # 0.00 segundos # >>> tiempo('subconjuntos3(range(14))') # 6.01 segundos # >>> tiempo('subconjuntos4(range(14))') # 0.00 segundos # # >>> tiempo('subconjuntos1(range(23))') # 1.95 segundos # >>> tiempo('subconjuntos2(range(23))') # 2.27 segundos # >>> tiempo('subconjuntos4(range(23))') # 1.62 segundos # Comprobación de la propiedad # ============================ # La propiedad es @given(st.lists(st.integers(), max_size=7)) def test_length_subconjuntos(xs: list[int]) -> None: assert len(subconjuntos1(xs)) == 2 ** len(xs) # La comprobación es # src> poetry run pytest -q subconjuntos_de_un_conjunto.py # 2 passed in 0.95s |