septiembre 2022 – Página 2

Divisores primos

PorJosé A. Alonso 23-septiembre-202214-diciembre-2022

Definir la función

   divisoresPrimos :: Integer -> [Integer]

1	divisoresPrimos :: Integer -> [Integer]

tal que divisoresPrimos x es la lista de los divisores primos de x. Por ejemplo,

   divisoresPrimos 40 == [2,5]
   divisoresPrimos 70 == [2,5,7]
   length (divisoresPrimos (product [1..20000])) == 2262

divisoresPrimos 40 == [2,5]

divisoresPrimos 70 == [2,5,7]

length (divisoresPrimos (product [1..20000])) == 2262

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

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)

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

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

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.

Divisores de un número

PorJosé A. Alonso 22-septiembre-202214-diciembre-2022

Definir la función

   divisores :: Integer -> [Integer]

1	divisores :: Integer -> [Integer]

tal que divisores n es la lista de los divisores de n. Por ejemplo,

  divisores 30  ==  [1,2,3,5,6,10,15,30]
  length (divisores (product [1..10]))  ==  270
  length (divisores (product [1..25]))  ==  340032

divisores 30 == [1,2,3,5,6,10,15,30]

length (divisores (product [1..10])) == 270

length (divisores (product [1..25])) == 340032

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

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)

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

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

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.

Diferencia conjuntista de listas

PorJosé A. Alonso 22-septiembre-202214-diciembre-2022

Definir la función

   diferencia :: Eq a => [a] -> [a] -> [a]

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,

   diferencia [3,2,5,6] [5,7,3,4]  ==  [2,6]
   diferencia [3,2,5] [5,7,3,2]    ==  []

1 2	diferencia [3,2,5,6] [5,7,3,4] == [2,6] diferencia [3,2,5] [5,7,3,2] == []

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

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)

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

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

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.

Intersección conjuntista de listas

PorJosé A. Alonso 21-septiembre-20222-septiembre-2022

Definir la función

   interseccion :: Eq a => [a] -> [a] -> [a]

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,

   interseccion [3,2,5] [5,7,3,4]  ==  [3,5]
   interseccion [3,2,5] [9,7,6,4]  ==  []

1 2	interseccion [3,2,5] [5,7,3,4] == [3,5] interseccion [3,2,5] [9,7,6,4] == []

Soluciones en Haskell

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)

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

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

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.

Unión conjuntista de listas

PorJosé A. Alonso 20-septiembre-202214-diciembre-2022

Definir la función

   union :: Ord a => [a] -> [a] -> [a]

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,

   union [3,2,5] [5,7,3,4]  ==  [3,2,5,7,4]

1	union [3,2,5] [5,7,3,4] == [3,2,5,7,4]

Comprobar con QuickCheck que la unión es conmutativa.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

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.

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

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

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

Meses: septiembre 2022

Divisores primos

Divisores de un número

Diferencia conjuntista de listas

Intersección conjuntista de listas

Unión conjuntista de listas

Entradas recientes

Buscar

Correo electrónico