PFH: La semana en Exercitium (23 de septiembre de 2022)
Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. Igualdad de conjuntos
- 2. Unión conjuntista de listas
- 3. Intersección conjuntista de listas
- 4. Diferencia conjuntista de listas
- 5. Divisores de un número
- 6. Divisores primos
A continuación se muestran las soluciones.
1. 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 en Haskell
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.
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 |
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 (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('iguales1(xs, xs)') # 2.71 segundos # >>> tiempo('iguales2(xs, xs)') # 0.01 segundos |
El código se encuentra en GitHub
2. Unión conjuntista de listas
Definir la función
1 |
union :: Ord a => [a] -> [a] -> [a] |
tal que union xs ys
es la unión de las listas, sin elementos repetidos, xs
e ys
. Por ejemplo,
1 |
union [3,2,5] [5,7,3,4] == [3,2,5,7,4] |
Comprobar con QuickCheck que la unión es conmutativa.
Soluciones en Haskell
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 |
import Data.List (nub, sort, union) import qualified Data.Set as S (fromList, toList, union) import Test.QuickCheck -- 1ª solución -- =========== union1 :: Ord a => [a] -> [a] -> [a] union1 xs ys = xs ++ [y | y <- ys, y `notElem` xs] -- 2ª solución -- =========== union2 :: Ord a => [a] -> [a] -> [a] union2 [] ys = ys union2 (x:xs) ys | x `elem` ys = xs `union2` ys | otherwise = x : xs `union2` ys -- 3ª solución -- =========== union3 :: Ord a => [a] -> [a] -> [a] union3 = union -- 4ª solución -- =========== union4 :: Ord a => [a] -> [a] -> [a] union4 xs ys = S.toList (S.fromList xs `S.union` S.fromList ys) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_union :: [Int] -> [Int] -> Bool prop_union xs ys = all (== sort (xs' `union1` ys')) [sort (xs' `union2` ys'), sort (xs' `union3` ys'), xs' `union4` ys'] where xs' = nub xs ys' = nub ys -- La comprobación es -- λ> quickCheck prop_union -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (union1 [0,2..3*10^4] [1,3..3*10^4]) -- 30001 -- (2.37 secs, 7,153,536 bytes) -- λ> length (union2 [0,2..3*10^4] [1,3..3*10^4]) -- 30001 -- (2.38 secs, 6,553,752 bytes) -- λ> length (union3 [0,2..3*10^4] [1,3..3*10^4]) -- 30001 -- (11.56 secs, 23,253,553,472 bytes) -- λ> length (union4 [0,2..3*10^4] [1,3..3*10^4]) -- 30001 -- (0.04 secs, 10,992,056 bytes) -- Comprobación de la propiedad -- ============================ -- La propiedad es prop_union_conmutativa :: [Int] -> [Int] -> Bool prop_union_conmutativa xs ys = iguales (xs `union1` ys) (ys `union1` xs) -- (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 = S.fromList xs == S.fromList ys -- La comprobación es -- λ> quickCheck prop_union_conmutativa -- +++ OK, passed 100 tests. |
El código se encuentra en GitHub.
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 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 99 100 |
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 union1(xs: list[A], ys: list[A]) -> list[A]: return xs + [y for y in ys if y not in xs] # 2ª solución # =========== def union2(xs: list[A], ys: list[A]) -> list[A]: if not xs: return ys if xs[0] in ys: return union2(xs[1:], ys) return [xs[0]] + union2(xs[1:], ys) # 3ª solución # =========== def union3(xs: list[A], ys: list[A]) -> list[A]: zs = ys[:] for x in xs: if x not in ys: zs.append(x) return zs # 4ª solución # =========== def union4(xs: list[A], ys: list[A]) -> list[A]: return list(set(xs) | set(ys)) # Comprobación de equivalencia # ============================ # # La propiedad es @given(st.lists(st.integers()), st.lists(st.integers())) def test_union(xs, ys): xs1 = list(set(xs)) ys1 = list(set(ys)) assert sorted(union1(xs1, ys1)) ==\ sorted(union2(xs1, ys1)) ==\ sorted(union3(xs1, ys1)) ==\ sorted(union4(xs1, ys1)) # La comprobación es # src> poetry run pytest -q union_conjuntista_de_listas.py # 1 passed in 0.36s # 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 # >>> tiempo('union1(list(range(0,30000,2)), list(range(1,30000,2)))') # 1.30 segundos # >>> tiempo('union2(list(range(0,30000,2)), list(range(1,30000,2)))') # 2.84 segundos # >>> tiempo('union3(list(range(0,30000,2)), list(range(1,30000,2)))') # 1.45 segundos # >>> tiempo('union4(list(range(0,30000,2)), list(range(1,30000,2)))') # 0.00 segundos # Comprobación de la propiedad # ============================ # iguales(xs, ys) se verifica si xs e ys son iguales como conjuntos. 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 def iguales(xs: list[A], ys: list[A]) -> bool: return set(xs) == set(ys) # La propiedad es @given(st.lists(st.integers()), st.lists(st.integers())) def test_union_conmutativa(xs, ys): xs1 = list(set(xs)) ys1 = list(set(ys)) assert iguales(union1(xs1, ys1), union1(ys1, xs1)) # La comprobación es # src> poetry run pytest -q union_conjuntista_de_listas.py # 2 passed in 0.49s |
El código se encuentra en GitHub
3. Intersección conjuntista de listas
Definir la función
1 |
interseccion :: Eq a => [a] -> [a] -> [a] |
tal que interseccion xs ys
es la intersección de las listas sin elementos repetidos xs
e ys
. Por ejemplo,
1 2 |
interseccion [3,2,5] [5,7,3,4] == [3,5] interseccion [3,2,5] [9,7,6,4] == [] |
Soluciones en Haskell
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 Data.List (nub, sort, intersect) import qualified Data.Set as S (fromList, toList, intersection ) import Test.QuickCheck -- 1ª solución -- =========== interseccion1 :: Eq a => [a] -> [a] -> [a] interseccion1 xs ys = [x | x <- xs, x `elem` ys] -- 2ª solución -- =========== interseccion2 :: Ord a => [a] -> [a] -> [a] interseccion2 [] _ = [] interseccion2 (x:xs) ys | x `elem` ys = x : xs `interseccion2` ys | otherwise = xs `interseccion2` ys -- 3ª solución -- =========== interseccion3 :: Ord a => [a] -> [a] -> [a] interseccion3 = intersect -- 4ª solución -- =========== interseccion4 :: Ord a => [a] -> [a] -> [a] interseccion4 xs ys = S.toList (S.fromList xs `S.intersection` S.fromList ys) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_interseccion :: [Int] -> [Int] -> Bool prop_interseccion xs ys = all (== sort (xs' `interseccion1` ys')) [sort (xs' `interseccion2` ys'), sort (xs' `interseccion3` ys'), xs' `interseccion4` ys'] where xs' = nub xs ys' = nub ys -- La comprobación es -- λ> quickCheck prop_interseccion -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (interseccion1 [0..3*10^4] [1,3..3*10^4]) -- 15000 -- (2.94 secs, 6,673,360 bytes) -- λ> length (interseccion2 [0..3*10^4] [1,3..3*10^4]) -- 15000 -- (3.04 secs, 9,793,440 bytes) -- λ> length (interseccion3 [0..3*10^4] [1,3..3*10^4]) -- 15000 -- (5.39 secs, 6,673,472 bytes) -- λ> length (interseccion4 [0..3*10^4] [1,3..3*10^4]) -- 15000 -- (0.04 secs, 8,593,176 bytes) |
El código se encuentra en GitHub.
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 70 71 72 73 74 75 76 |
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 interseccion1(xs: list[A], ys: list[A]) -> list[A]: return [x for x in xs if x in ys] # 2ª solución # =========== def interseccion2(xs: list[A], ys: list[A]) -> list[A]: if not xs: return [] if xs[0] in ys: return [xs[0]] + interseccion2(xs[1:], ys) return interseccion2(xs[1:], ys) # 3ª solución # =========== def interseccion3(xs: list[A], ys: list[A]) -> list[A]: zs = [] for x in xs: if x in ys: zs.append(x) return zs # 4ª solución # =========== def interseccion4(xs: list[A], ys: list[A]) -> list[A]: return list(set(xs) & set(ys)) # Comprobación de equivalencia # ============================ # # La propiedad es @given(st.lists(st.integers()), st.lists(st.integers())) def test_interseccion(xs, ys): xs1 = list(set(xs)) ys1 = list(set(ys)) assert sorted(interseccion1(xs1, ys1)) ==\ sorted(interseccion2(xs1, ys1)) ==\ sorted(interseccion3(xs1, ys1)) ==\ sorted(interseccion4(xs1, ys1)) # La comprobación es # src> poetry run pytest -q interseccion_conjuntista_de_listas.py # 1 passed in 0.33s # 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 # >>> tiempo('interseccion1(list(range(0,20000)), list(range(1,20000,2)))') # 0.98 segundos # >>> tiempo('interseccion2(list(range(0,20000)), list(range(1,20000,2)))') # 2.13 segundos # >>> tiempo('interseccion3(list(range(0,20000)), list(range(1,20000,2)))') # 0.87 segundos # >>> tiempo('interseccion4(list(range(0,20000)), list(range(1,20000,2)))') # 0.00 segundos |
El código se encuentra en GitHub.
4. Diferencia conjuntista de listas
Definir la función
1 |
diferencia :: Eq a => [a] -> [a] -> [a] |
tal que diferencia xs ys
es la diferencia de las listas sin elementos repetidos xs
e ys
. Por ejemplo,
1 2 |
diferencia [3,2,5,6] [5,7,3,4] == [2,6] diferencia [3,2,5] [5,7,3,2] == [] |
Soluciones en Haskell
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 Data.List (nub, sort, (\\)) import qualified Data.Set as S (fromList, toList, (\\) ) import Test.QuickCheck -- 1ª solución -- =========== diferencia1 :: Eq a => [a] -> [a] -> [a] diferencia1 xs ys = [x | x <- xs, x `notElem` ys] -- 2ª solución -- =========== diferencia2 :: Ord a => [a] -> [a] -> [a] diferencia2 [] _ = [] diferencia2 (x:xs) ys | x `elem` ys = xs `diferencia2` ys | otherwise = x : xs `diferencia2` ys -- 3ª solución -- =========== diferencia3 :: Ord a => [a] -> [a] -> [a] diferencia3 = (\\) -- 4ª solución -- =========== diferencia4 :: Ord a => [a] -> [a] -> [a] diferencia4 xs ys = S.toList (S.fromList xs S.\\ S.fromList ys) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_diferencia :: [Int] -> [Int] -> Bool prop_diferencia xs ys = all (== sort (xs' `diferencia1` ys')) [sort (xs' `diferencia2` ys'), sort (xs' `diferencia3` ys'), xs' `diferencia4` ys'] where xs' = nub xs ys' = nub ys -- La comprobación es -- λ> quickCheck prop_diferencia -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (diferencia1 [0..3*10^4] [1,3..3*10^4]) -- 15001 -- (3.39 secs, 9,553,528 bytes) -- λ> length (diferencia2 [0..3*10^4] [1,3..3*10^4]) -- 15001 -- (2.98 secs, 9,793,528 bytes) -- λ> length (diferencia3 [0..3*10^4] [1,3..3*10^4]) -- 15001 -- (3.61 secs, 11,622,502,792 bytes) -- λ> length (diferencia4 [0..3*10^4] [1,3..3*10^4]) -- 15001 -- (0.02 secs, 10,092,832 bytes) |
El código se encuentra en GitHub.
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 70 71 72 73 74 75 76 |
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 diferencia1(xs: list[A], ys: list[A]) -> list[A]: return [x for x in xs if x not in ys] # 2ª solución # =========== def diferencia2(xs: list[A], ys: list[A]) -> list[A]: if not xs: return [] if xs[0] in ys: return diferencia2(xs[1:], ys) return [xs[0]] + diferencia2(xs[1:], ys) # 3ª solución # =========== def diferencia3(xs: list[A], ys: list[A]) -> list[A]: zs = [] for x in xs: if x not in ys: zs.append(x) return zs # 4ª solución # =========== def diferencia4(xs: list[A], ys: list[A]) -> list[A]: return list(set(xs) - set(ys)) # Comprobación de equivalencia # ============================ # # La propiedad es @given(st.lists(st.integers()), st.lists(st.integers())) def test_diferencia(xs, ys): xs1 = list(set(xs)) ys1 = list(set(ys)) assert sorted(diferencia1(xs1, ys1)) ==\ sorted(diferencia2(xs1, ys1)) ==\ sorted(diferencia3(xs1, ys1)) ==\ sorted(diferencia4(xs1, ys1)) # La comprobación es # src> poetry run pytest -q diferencia_conjuntista_de_listas.py # 1 passed in 0.39s # 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 # >>> tiempo('diferencia1(list(range(0,20000)), list(range(1,20000,2)))') # 0.89 segundos # >>> tiempo('diferencia2(list(range(0,20000)), list(range(1,20000,2)))') # 2.11 segundos # >>> tiempo('diferencia3(list(range(0,20000)), list(range(1,20000,2)))') # 1.06 segundos # >>> tiempo('diferencia4(list(range(0,20000)), list(range(1,20000,2)))') # 0.01 segundos |
El código se encuentra en GitHub.
5. Divisores de un número
Definir la función
1 |
divisores :: Integer -> [Integer] |
tal que divisores n
es la lista de los divisores de n
. Por ejemplo,
1 2 3 |
divisores 30 == [1,2,3,5,6,10,15,30] length (divisores (product [1..10])) == 270 length (divisores (product [1..25])) == 340032 |
Soluciones en Haskell
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 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 |
import Data.List (group, inits, nub, sort, subsequences) import Data.Numbers.Primes (primeFactors) import Data.Set (toList) import Math.NumberTheory.ArithmeticFunctions (divisors) import Test.QuickCheck -- 1ª solución -- =========== divisores1 :: Integer -> [Integer] divisores1 n = [x | x <- [1..n], n `rem` x == 0] -- 2ª solución -- =========== divisores2 :: Integer -> [Integer] divisores2 n = [x | x <- [1..n], x `esDivisorDe` n] -- (esDivisorDe x n) se verifica si x es un divisor de n. Por ejemplo, -- esDivisorDe 2 6 == True -- esDivisorDe 4 6 == False esDivisorDe :: Integer -> Integer -> Bool esDivisorDe x n = n `rem` x == 0 -- 3ª solución -- =========== divisores3 :: Integer -> [Integer] divisores3 n = filter (`esDivisorDe` n) [1..n] -- 4ª solución -- =========== divisores4 :: Integer -> [Integer] divisores4 = filter <$> flip esDivisorDe <*> enumFromTo 1 -- 5ª solución -- =========== divisores5 :: Integer -> [Integer] divisores5 n = xs ++ [n `div` y | y <- ys] where xs = primerosDivisores1 n (z:zs) = reverse xs ys | z^2 == n = zs | otherwise = z:zs -- (primerosDivisores n) es la lista de los divisores del número n cuyo -- cuadrado es menor o gual que n. Por ejemplo, -- primerosDivisores 25 == [1,5] -- primerosDivisores 30 == [1,2,3,5] primerosDivisores1 :: Integer -> [Integer] primerosDivisores1 n = [x | x <- [1..round (sqrt (fromIntegral n))], x `esDivisorDe` n] -- 6ª solución -- =========== divisores6 :: Integer -> [Integer] divisores6 n = aux [1..n] where aux [] = [] aux (x:xs) | x `esDivisorDe` n = x : aux xs | otherwise = aux xs -- 7ª solución -- =========== divisores7 :: Integer -> [Integer] divisores7 n = xs ++ [n `div` y | y <- ys] where xs = primerosDivisores2 n (z:zs) = reverse xs ys | z^2 == n = zs | otherwise = z:zs primerosDivisores2 :: Integer -> [Integer] primerosDivisores2 n = aux [1..round (sqrt (fromIntegral n))] where aux [] = [] aux (x:xs) | x `esDivisorDe` n = x : aux xs | otherwise = aux xs -- 8ª solución -- =========== divisores8 :: Integer -> [Integer] divisores8 = nub . sort . map product . subsequences . primeFactors -- 9ª solución -- =========== divisores9 :: Integer -> [Integer] divisores9 = sort . map (product . concat) . productoCartesiano . map inits . group . primeFactors -- (productoCartesiano xss) es el producto cartesiano de los conjuntos -- xss. Por ejemplo, -- λ> productoCartesiano [[1,3],[2,5],[6,4]] -- [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]] productoCartesiano :: [[a]] -> [[a]] productoCartesiano [] = [[]] productoCartesiano (xs:xss) = [x:ys | x <- xs, ys <- productoCartesiano xss] -- 10ª solución -- ============ divisores10 :: Integer -> [Integer] divisores10 = sort . map (product . concat) . mapM inits . group . primeFactors -- 11ª solución -- ============ divisores11 :: Integer -> [Integer] divisores11 = toList . divisors -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_divisores :: Positive Integer -> Bool prop_divisores (Positive n) = all (== divisores1 n) [ divisores2 n , divisores3 n , divisores4 n , divisores5 n , divisores6 n , divisores7 n , divisores8 n , divisores9 n , divisores10 n , divisores11 n ] -- La comprobación es -- λ> quickCheck prop_divisores -- +++ OK, passed 100 tests. -- Comparación de la eficiencia -- ============================ -- La comparación es -- λ> length (divisores1 (product [1..11])) -- 540 -- (18.55 secs, 7,983,950,592 bytes) -- λ> length (divisores2 (product [1..11])) -- 540 -- (18.81 secs, 7,983,950,592 bytes) -- λ> length (divisores3 (product [1..11])) -- 540 -- (12.79 secs, 6,067,935,544 bytes) -- λ> length (divisores4 (product [1..11])) -- 540 -- (12.51 secs, 6,067,935,592 bytes) -- λ> length (divisores5 (product [1..11])) -- 540 -- (0.03 secs, 1,890,296 bytes) -- λ> length (divisores6 (product [1..11])) -- 540 -- (21.46 secs, 9,899,961,392 bytes) -- λ> length (divisores7 (product [1..11])) -- 540 -- (0.02 secs, 2,195,800 bytes) -- λ> length (divisores8 (product [1..11])) -- 540 -- (0.09 secs, 107,787,272 bytes) -- λ> length (divisores9 (product [1..11])) -- 540 -- (0.02 secs, 2,150,472 bytes) -- λ> length (divisores10 (product [1..11])) -- 540 -- (0.01 secs, 1,652,120 bytes) -- λ> length (divisores11 (product [1..11])) -- 540 -- (0.01 secs, 796,056 bytes) -- -- λ> length (divisores5 (product [1..17])) -- 10752 -- (10.16 secs, 3,773,953,128 bytes) -- λ> length (divisores7 (product [1..17])) -- 10752 -- (9.83 secs, 4,679,260,712 bytes) -- λ> length (divisores9 (product [1..17])) -- 10752 -- (0.06 secs, 46,953,344 bytes) -- λ> length (divisores10 (product [1..17])) -- 10752 -- (0.02 secs, 33,633,712 bytes) -- λ> length (divisores11 (product [1..17])) -- 10752 -- (0.03 secs, 6,129,584 bytes) -- -- λ> length (divisores10 (product [1..27])) -- 677376 -- (2.14 secs, 3,291,277,736 bytes) -- λ> length (divisores11 (product [1..27])) -- 677376 -- (0.56 secs, 396,042,280 bytes) |
El código se encuentra en GitHub.
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 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 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 |
from math import factorial, sqrt from timeit import Timer, default_timer from sys import setrecursionlimit from sympy import divisors from hypothesis import given, strategies as st setrecursionlimit(10**6) # 1ª solución # =========== def divisores1(n: int) -> list[int]: return [x for x in range(1, n + 1) if n % x == 0] # 2ª solución # =========== # esDivisorDe(x, n) se verifica si x es un divisor de n. Por ejemplo, # esDivisorDe(2, 6) == True # esDivisorDe(4, 6) == False def esDivisorDe(x: int, n: int) -> bool: return n % x == 0 def divisores2(n: int) -> list[int]: return [x for x in range(1, n + 1) if esDivisorDe(x, n)] # 3ª solución # =========== def divisores3(n: int) -> list[int]: return list(filter(lambda x: esDivisorDe(x, n), range(1, n + 1))) # 4ª solución # =========== # primerosDivisores(n) es la lista de los divisores del número n cuyo # cuadrado es menor o gual que n. Por ejemplo, # primerosDivisores(25) == [1,5] # primerosDivisores(30) == [1,2,3,5] def primerosDivisores(n: int) -> list[int]: return [x for x in range(1, 1 + round(sqrt(n))) if n % x == 0] def divisores4(n: int) -> list[int]: xs = primerosDivisores(n) zs = list(reversed(xs)) if zs[0]**2 == n: return xs + [n // a for a in zs[1:]] return xs + [n // a for a in zs] # 5ª solución # =========== def divisores5(n: int) -> list[int]: def aux(xs: list[int]) -> list[int]: if xs: if esDivisorDe(xs[0], n): return [xs[0]] + aux(xs[1:]) return aux(xs[1:]) return xs return aux(list(range(1, n + 1))) # 6ª solución # ============ def divisores6(n: int) -> list[int]: xs = [] for x in range(1, n+1): if n % x == 0: xs.append(x) return xs # 7ª solución # =========== def divisores7(n: int) -> list[int]: x = 1 xs = [] ys = [] while x * x < n: if n % x == 0: xs.append(x) ys.append(n // x) x = x + 1 if x * x == n: xs.append(x) return xs + list(reversed(ys)) # 8ª solución # ============ def divisores8(n: int) -> list[int]: return divisors(n) # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=2, max_value=1000)) def test_divisores(n): assert divisores1(n) ==\ divisores2(n) ==\ divisores3(n) ==\ divisores4(n) ==\ divisores5(n) ==\ divisores6(n) ==\ divisores7(n) ==\ divisores8(n) # La comprobación es # src> poetry run pytest -q divisores_de_un_numero.py # 1 passed in 0.84s # 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 # >>> tiempo('divisores5(4*factorial(7))') # 1.40 segundos # # >>> tiempo('divisores1(factorial(11))') # 1.79 segundos # >>> tiempo('divisores2(factorial(11))') # 3.80 segundos # >>> tiempo('divisores3(factorial(11))') # 5.22 segundos # >>> tiempo('divisores4(factorial(11))') # 0.00 segundos # >>> tiempo('divisores6(factorial(11))') # 3.51 segundos # >>> tiempo('divisores7(factorial(11))') # 0.00 segundos # >>> tiempo('divisores8(factorial(11))') # 0.00 segundos # # >>> tiempo('divisores4(factorial(17))') # 2.23 segundos # >>> tiempo('divisores7(factorial(17))') # 3.22 segundos # >>> tiempo('divisores8(factorial(17))') # 0.00 segundos # # >>> tiempo('divisores8(factorial(27))') # 0.28 segundos |
El código se encuentra en GitHub.
6. Divisores primos
Definir la función
1 |
divisoresPrimos :: Integer -> [Integer] |
tal que divisoresPrimos x
es la lista de los divisores primos de x
. Por ejemplo,
1 2 3 |
divisoresPrimos 40 == [2,5] divisoresPrimos 70 == [2,5,7] length (divisoresPrimos (product [1..20000])) == 2262 |
Soluciones en Haskell
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 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 |
import Data.List (nub) import Data.Set (toList) import Data.Numbers.Primes (isPrime, primeFactors) import Math.NumberTheory.ArithmeticFunctions (divisors) import Test.QuickCheck -- 1ª solución -- =========== divisoresPrimos1 :: Integer -> [Integer] divisoresPrimos1 x = [n | n <- divisores1 x, primo1 n] -- (divisores n) es la lista de los divisores del número n. Por ejemplo, -- divisores 25 == [1,5,25] -- divisores 30 == [1,2,3,5,6,10,15,30] divisores1 :: Integer -> [Integer] divisores1 n = [x | x <- [1..n], n `mod` x == 0] -- (primo n) se verifica si n es primo. Por ejemplo, -- primo 30 == False -- primo 31 == True primo1 :: Integer -> Bool primo1 n = divisores1 n == [1, n] -- 2ª solución -- =========== divisoresPrimos2 :: Integer -> [Integer] divisoresPrimos2 x = [n | n <- divisores2 x, primo2 n] divisores2 :: Integer -> [Integer] divisores2 n = xs ++ [n `div` y | y <- ys] where xs = primerosDivisores2 n (z:zs) = reverse xs ys | z^2 == n = zs | otherwise = z:zs -- (primerosDivisores n) es la lista de los divisores del número n cuyo -- cuadrado es menor o gual que n. Por ejemplo, -- primerosDivisores 25 == [1,5] -- primerosDivisores 30 == [1,2,3,5] primerosDivisores2 :: Integer -> [Integer] primerosDivisores2 n = [x | x <- [1..round (sqrt (fromIntegral n))], n `mod` x == 0] primo2 :: Integer -> Bool primo2 1 = False primo2 n = primerosDivisores2 n == [1] -- 3ª solución -- =========== divisoresPrimos3 :: Integer -> [Integer] divisoresPrimos3 x = [n | n <- divisores3 x, primo3 n] divisores3 :: Integer -> [Integer] divisores3 n = xs ++ [n `div` y | y <- ys] where xs = primerosDivisores3 n (z:zs) = reverse xs ys | z^2 == n = zs | otherwise = z:zs primerosDivisores3 :: Integer -> [Integer] primerosDivisores3 n = filter ((== 0) . mod n) [1..round (sqrt (fromIntegral n))] primo3 :: Integer -> Bool primo3 1 = False primo3 n = primerosDivisores3 n == [1] -- 4ª solución -- =========== divisoresPrimos4 :: Integer -> [Integer] divisoresPrimos4 n | even n = 2 : divisoresPrimos4 (reducido n 2) | otherwise = aux n [3,5..n] where aux 1 _ = [] aux _ [] = [] aux m (x:xs) | m `mod` x == 0 = x : aux (reducido m x) xs | otherwise = aux m xs -- (reducido m x) es el resultado de dividir repetidamente m por x, -- mientras sea divisible. Por ejemplo, -- reducido 36 2 == 9 reducido :: Integer -> Integer -> Integer reducido m x | m `mod` x == 0 = reducido (m `div` x) x | otherwise = m -- 5ª solución -- =========== divisoresPrimos5 :: Integer -> [Integer] divisoresPrimos5 = nub . primeFactors -- 6ª solución -- =========== divisoresPrimos6 :: Integer -> [Integer] divisoresPrimos6 = filter isPrime . toList . divisors -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_divisoresPrimos :: Integer -> Property prop_divisoresPrimos n = n > 1 ==> all (== divisoresPrimos1 n) [divisoresPrimos2 n, divisoresPrimos3 n, divisoresPrimos4 n, divisoresPrimos5 n, divisoresPrimos6 n] -- La comprobación es -- λ> quickCheck prop_divisoresPrimos -- +++ OK, passed 100 tests; 108 discarded. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> divisoresPrimos1 (product [1..11]) -- [2,3,5,7,11] -- (18.34 secs, 7,984,382,104 bytes) -- λ> divisoresPrimos2 (product [1..11]) -- [2,3,5,7,11] -- (0.02 secs, 2,610,976 bytes) -- λ> divisoresPrimos3 (product [1..11]) -- [2,3,5,7,11] -- (0.02 secs, 2,078,288 bytes) -- λ> divisoresPrimos4 (product [1..11]) -- [2,3,5,7,11] -- (0.02 secs, 565,992 bytes) -- λ> divisoresPrimos5 (product [1..11]) -- [2,3,5,7,11] -- (0.01 secs, 568,000 bytes) -- λ> divisoresPrimos6 (product [1..11]) -- [2,3,5,7,11] -- (0.00 secs, 2,343,392 bytes) -- -- λ> divisoresPrimos2 (product [1..16]) -- [2,3,5,7,11,13] -- (2.32 secs, 923,142,480 bytes) -- λ> divisoresPrimos3 (product [1..16]) -- [2,3,5,7,11,13] -- (0.80 secs, 556,961,088 bytes) -- λ> divisoresPrimos4 (product [1..16]) -- [2,3,5,7,11,13] -- (0.01 secs, 572,368 bytes) -- λ> divisoresPrimos5 (product [1..16]) -- [2,3,5,7,11,13] -- (0.01 secs, 31,665,896 bytes) -- λ> divisoresPrimos6 (product [1..16]) -- [2,3,5,7,11,13] -- (0.01 secs, 18,580,584 bytes) -- -- λ> length (divisoresPrimos4 (product [1..30])) -- 10 -- (0.01 secs, 579,168 bytes) -- λ> length (divisoresPrimos5 (product [1..30])) -- 10 -- (0.01 secs, 594,976 bytes) -- λ> length (divisoresPrimos6 (product [1..30])) -- 10 -- (3.38 secs, 8,068,783,408 bytes) -- -- λ> length (divisoresPrimos4 (product [1..20000])) -- 2262 -- (1.20 secs, 1,940,069,976 bytes) -- λ> length (divisoresPrimos5 (product [1..20000])) -- 2262 -- (1.12 secs, 1,955,921,736 bytes) |
El código se encuentra en GitHub.
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 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 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 |
from math import sqrt from operator import mul from functools import reduce from timeit import Timer, default_timer from sys import setrecursionlimit from sympy import divisors, isprime, primefactors from hypothesis import given, strategies as st setrecursionlimit(10**6) # 1ª solución # =========== # divisores(n) es la lista de los divisores del número n. Por ejemplo, # divisores(30) == [1,2,3,5,6,10,15,30] def divisores1(n: int) -> list[int]: return [x for x in range(1, n + 1) if n % x == 0] # primo(n) se verifica si n es primo. Por ejemplo, # primo(30) == False # primo(31) == True def primo1(n: int) -> bool: return divisores1(n) == [1, n] def divisoresPrimos1(x: int) -> list[int]: return [n for n in divisores1(x) if primo1(n)] # 2ª solución # =========== # primerosDivisores(n) es la lista de los divisores del número n cuyo # cuadrado es menor o gual que n. Por ejemplo, # primerosDivisores(25) == [1,5] # primerosDivisores(30) == [1,2,3,5] def primerosDivisores2(n: int) -> list[int]: return [x for x in range(1, 1 + round(sqrt(n))) if n % x == 0] def divisores2(n: int) -> list[int]: xs = primerosDivisores2(n) zs = list(reversed(xs)) if zs[0]**2 == n: return xs + [n // a for a in zs[1:]] return xs + [n // a for a in zs] def primo2(n: int) -> bool: return divisores2(n) == [1, n] def divisoresPrimos2(x: int) -> list[int]: return [n for n in divisores2(x) if primo2(n)] # 3ª solución # =========== # reducido(m, x) es el resultado de dividir repetidamente m por x, # mientras sea divisible. Por ejemplo, # reducido(36, 2) == 9 def reducido(m: int, x: int) -> int: if m % x == 0: return reducido(m // x, x) return m def divisoresPrimos3(n: int) -> list[int]: if n % 2 == 0: return [2] + divisoresPrimos3(reducido(n, 2)) def aux(m, xs): if m == 1: return [] if xs == []: return [] if m % xs[0] == 0: return [xs[0]] + aux(reducido(m, xs[0]), xs[1:]) return aux(m, xs[1:]) return aux(n, range(3, n + 1, 2)) # 4ª solución # =========== def divisoresPrimos4(x: int) -> list[int]: return [n for n in divisors(x) if isprime(n)] # 5ª solución # =========== def divisoresPrimos5(n): return primefactors(n) # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=2, max_value=1000)) def test_divisoresPrimos(n): assert divisoresPrimos1(n) ==\ divisoresPrimos2(n) ==\ divisoresPrimos3(n) ==\ divisoresPrimos4(n) ==\ divisoresPrimos5(n) # La comprobación es # src> poetry run pytest -q divisores_primos.py # 1 passed in 0.70s # 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") def producto(xs: list[int]) -> int: return reduce(mul, xs) # La comparación es # >>> tiempo('divisoresPrimos1(producto(list(range(1, 12))))') # 11.14 segundos # >>> tiempo('divisoresPrimos2(producto(list(range(1, 12))))') # 0.03 segundos # >>> tiempo('divisoresPrimos3(producto(list(range(1, 12))))') # 0.00 segundos # >>> tiempo('divisoresPrimos4(producto(list(range(1, 12))))') # 0.00 segundos # >>> tiempo('divisoresPrimos5(producto(list(range(1, 12))))') # 0.00 segundos # # >>> tiempo('divisoresPrimos2(producto(list(range(1, 17))))') # 14.21 segundos # >>> tiempo('divisoresPrimos3(producto(list(range(1, 17))))') # 0.00 segundos # >>> tiempo('divisoresPrimos4(producto(list(range(1, 17))))') # 0.01 segundos # >>> tiempo('divisoresPrimos5(producto(list(range(1, 17))))') # 0.00 segundos # # >>> tiempo('divisoresPrimos3(producto(list(range(1, 32))))') # 0.00 segundos # >>> tiempo('divisoresPrimos4(producto(list(range(1, 32))))') # 4.59 segundos # >>> tiempo('divisoresPrimos5(producto(list(range(1, 32))))') # 0.00 segundos # # >>> tiempo('divisoresPrimos3(producto(list(range(1, 10001))))') # 3.00 segundos # >>> tiempo('divisoresPrimos5(producto(list(range(1, 10001))))') # 0.24 segundos |
El código se encuentra en GitHub.