Reconocimiento de subconjunto

Definir la función

   subconjunto :: Ord a => [a] -> [a] -> Bool

1	subconjunto :: Ord a => [a] -> [a] -> Bool

tal que 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

1 2	subconjunto [3,2,3] [2,5,3,5] == True subconjunto [3,2,3] [2,5,6,5] == False

Soluciones

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

Soluciones en Haskell

module Reconocimiento_de_subconjunto where

import Data.List (nub, sort)
import Data.Set (fromList, isSubsetOf)
import Test.QuickCheck

-- 1ª solución
subconjunto1 :: Ord a => [a] -> [a] -> Bool
subconjunto1 xs ys =
  [x | x <- xs, x `elem` ys] == xs

-- 2ª solución
subconjunto2 :: Ord a => [a] -> [a] -> Bool
subconjunto2 []     _  = True
subconjunto2 (x:xs) ys = x `elem` ys && subconjunto2 xs ys

-- 3ª solución
subconjunto3 :: Ord a => [a] -> [a] -> Bool
subconjunto3 xs ys =
  all (`elem` ys) xs

-- 4ª solución
subconjunto4 :: Ord a => [a] -> [a] -> Bool
subconjunto4 xs ys =
  fromList xs `isSubsetOf` fromList ys

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_subconjunto :: [Int] -> [Int] -> Bool
prop_subconjunto xs ys =
  all (== subconjunto1 xs ys)
      [subconjunto2 xs ys,
       subconjunto3 xs ys,
       subconjunto4 xs ys]

-- La comprobación es
--    λ> quickCheck prop_subconjunto
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> subconjunto1 [1..2*10^4] [1..2*10^4]
--    True
--    (1.81 secs, 5,992,448 bytes)
--    λ> subconjunto2 [1..2*10^4] [1..2*10^4]
--    True
--    (1.83 secs, 6,952,200 bytes)
--    λ> subconjunto3 [1..2*10^4] [1..2*10^4]
--    True
--    (1.75 secs, 4,712,304 bytes)
--    λ> subconjunto4 [1..2*10^4] [1..2*10^4]
--    True
--    (0.04 secs, 6,312,056 bytes)

module Reconocimiento_de_subconjunto where

import Data.List (nub, sort)

import Data.Set (fromList, isSubsetOf)

import Test.QuickCheck

-- 1ª solución

subconjunto1 :: Ord a => [a] -> [a] -> Bool

subconjunto1 xs ys =

[x | x <- xs, x `elem` ys] == xs

-- 2ª solución

subconjunto2 :: Ord a => [a] -> [a] -> Bool

subconjunto2 [] _ = True

subconjunto2 (x:xs) ys = x `elem` ys && subconjunto2 xs ys

-- 3ª solución

subconjunto3 :: Ord a => [a] -> [a] -> Bool

subconjunto3 xs ys =

all (`elem` ys) xs

-- 4ª solución

subconjunto4 :: Ord a => [a] -> [a] -> Bool

subconjunto4 xs ys =

fromList xs `isSubsetOf` fromList ys

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_subconjunto :: [Int] -> [Int] -> Bool

prop_subconjunto xs ys =

all (== subconjunto1 xs ys)

[subconjunto2 xs ys,

subconjunto3 xs ys,

subconjunto4 xs ys]

-- La comprobación es

-- λ> quickCheck prop_subconjunto

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> subconjunto1 [1..2*10^4] [1..2*10^4]

-- True

-- (1.81 secs, 5,992,448 bytes)

-- λ> subconjunto2 [1..2*10^4] [1..2*10^4]

-- True

-- (1.83 secs, 6,952,200 bytes)

-- λ> subconjunto3 [1..2*10^4] [1..2*10^4]

-- True

-- (1.75 secs, 4,712,304 bytes)

-- λ> subconjunto4 [1..2*10^4] [1..2*10^4]

-- True

-- (0.04 secs, 6,312,056 bytes)

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 subconjunto1(xs: list[A],
                 ys: list[A]) -> bool:
    return [x for x in xs if x in ys] == xs

# 2ª solución
def subconjunto2(xs: list[A],
                 ys: list[A]) -> bool:
    if xs:
        return xs[0] in ys and subconjunto2(xs[1:], ys)
    return True

# 3ª solución
def subconjunto3(xs: list[A],
                 ys: list[A]) -> bool:
    return all(x in ys for x in xs)

# 4ª solución
def subconjunto4(xs: list[A],
                 ys: list[A]) -> bool:
    return set(xs) <= set(ys)

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_subconjunto(xs, ys):
    assert subconjunto1(xs, ys)\
           == subconjunto2(xs, ys)\
           == subconjunto3(xs, ys)\
           == subconjunto4(xs, ys)

# La comprobación es
#    src> poetry run pytest -q reconocimiento_de_subconjunto.py
#    1 passed in 0.34s

# 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('subconjunto1(xs, xs)')
#    1.27 segundos
#    >>> tiempo('subconjunto2(xs, xs)')
#    1.84 segundos
#    >>> tiempo('subconjunto3(xs, xs)')
#    1.19 segundos
#    >>> tiempo('subconjunto4(xs, xs)')
#    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 subconjunto1(xs: list[A],

ys: list[A]) -> bool:

return [x for x in xs if x in ys] == xs

# 2ª solución

def subconjunto2(xs: list[A],

ys: list[A]) -> bool:

if xs:

return xs[0] in ys and subconjunto2(xs[1:], ys)

return True

# 3ª solución

def subconjunto3(xs: list[A],

ys: list[A]) -> bool:

return all(x in ys for x in xs)

# 4ª solución

def subconjunto4(xs: list[A],

ys: list[A]) -> bool:

return set(xs) <= set(ys)

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.lists(st.integers()),

st.lists(st.integers()))

def test_subconjunto(xs, ys):

assert subconjunto1(xs, ys)\

== subconjunto2(xs, ys)\

== subconjunto3(xs, ys)\

== subconjunto4(xs, ys)

# La comprobación es

# src> poetry run pytest -q reconocimiento_de_subconjunto.py

# 1 passed in 0.34s

# 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('subconjunto1(xs, xs)')

# 1.27 segundos

# >>> tiempo('subconjunto2(xs, xs)')

# 1.84 segundos

# >>> tiempo('subconjunto3(xs, xs)')

# 1.19 segundos

# >>> tiempo('subconjunto4(xs, xs)')

# 0.01 segundos

El código se encuentra en GitHub.

Comentarios

La expresión «x pertenece a ys» se escribe
- en Haskell, como x `elem` ys
- en Python, como x in ys
La expresión «todos los elementos de xs verifican la propiedad p» se escribe
- en Haskell, como all p xs
- en Python, como all(p(x) for x in xs)
Si xs e ys son conjuntos, la expresión «xs es subconjunto de ys» se escribe
- en Haskell, como xs `isSubsetOf` ys
- en Python, como xs <= ys

Reconocimiento de subconjunto

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Se puede imprimir o compartir con

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico