Menu Close

Etiqueta: Relaciones binarias

Relaciones simétricas

José A. Alonso, ,

Usando el tipo de las relaciones binarias, definir la función

   simetrica :: Eq a => Rel a -> Bool

tal que simetrica r se verifica si la relación r es simétrica. Por ejemplo,

   simetrica (R ([1,3],[(1,1),(1,3),(3,1)]))  ==  True
   simetrica (R ([1,3],[(1,1),(1,3),(3,2)]))  ==  False
   simetrica (R ([1,3],[]))                   ==  True

Soluciones

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


Soluciones en Haskell

import Relaciones_binarias (Rel(R))
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
simetrica :: Eq a => Rel a -> Bool
simetrica (R (_,g)) = and [(y,x) `elem` g | (x,y) <- g]
 
-- 2ª solución
-- ===========
 
simetrica2 :: Eq a => Rel a -> Bool
simetrica2 (R (_,g)) = all (\(x,y) -> (y,x) `elem` g) g
 
-- 3ª solución
-- ===========
 
simetrica3 :: Eq a => Rel a -> Bool
simetrica3 (R (_,g)) = aux g
  where aux [] = True
        aux ((x,y):ps) = (y,x) `elem` g && aux ps
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_simetrica :: Rel Int -> Bool
prop_simetrica r =
  all (== simetrica r)
      [simetrica2 r,
       simetrica3 r]
 
-- La comprobación es
--    λ> quickCheck prop_simetrica
--    +++ OK, passed 100 tests.


Soluciones en Python

from typing import TypeVar
 
from hypothesis import given
from hypothesis import strategies as st
 
from src.Relaciones_binarias import Rel, relacionArbitraria
 
A = TypeVar('A')
 
# 1ª solución
# ===========
 
def simetrica(r: Rel[A]) -> bool:
    (_, g) = r
    return all(((y, x) in g for (x, y) in g))
 
# 2ª solución
# ===========
 
def simetrica2(r: Rel[A]) -> bool:
    (_, g) = r
    def aux(ps: list[tuple[A, A]]) -> bool:
        if not ps:
            return True
        (x, y) = ps[0]
        return (y, x) in g and aux(ps[1:])
 
    return aux(g)
 
# 3ª solución
# ===========
 
def simetrica3(r: Rel[A]) -> bool:
    (_, g) = r
    for (x, y) in g:
        if (y, x) not in g:
            return False
    return True
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.integers(min_value=0, max_value=10))
def test_simetrica(n: int) -> None:
    r = relacionArbitraria(n)
    res = simetrica(r)
    assert simetrica2(r) == res
    assert simetrica3(r) == res
 
# La comprobación es
#    > poetry run pytest -q Relaciones_simetricas.py
#    1 passed in 0.11s
Leer más →

Relaciones reflexivas

José A. Alonso, ,

Usando el tipo de las relaciones binarias, definir la función

   reflexiva :: Eq a => Rel a -> Bool

tal que reflexiva r se verifica si la relación r es reflexiva. Por ejemplo,

   reflexiva (R ([1,3],[(1,1),(1,3),(3,3)]))    ==  True
   reflexiva (R ([1,2,3],[(1,1),(1,3),(3,3)]))  ==  False

Soluciones

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


Soluciones en Haskell

module Relaciones_reflexivas where
 
import Relaciones_binarias (Rel(R))
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
reflexiva :: Eq a => Rel a -> Bool
reflexiva (R ([], _))   = True
reflexiva (R (x:xs, ps)) = (x, x) `elem` ps && reflexiva  (R (xs, ps))
 
-- 2ª solución
-- ===========
 
reflexiva2 :: Eq a => Rel a -> Bool
reflexiva2 (R (us,ps)) = and [(x,x) `elem` ps | x <- us]
 
-- 3ª solución
-- ===========
 
reflexiva3 :: Eq a => Rel a -> Bool
reflexiva3 (R (us,ps)) = all (`elem` ps) [(x,x) | x <- us]
 
-- 4ª solución
-- ===========
 
reflexiva4 :: Eq a => Rel a -> Bool
reflexiva4 (R (us,ps)) = all (\x -> (x,x) `elem` ps) us
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_reflexiva :: Rel Int -> Bool
prop_reflexiva r =
  all (== reflexiva r)
      [reflexiva2 r,
       reflexiva3 r,
       reflexiva4 r]
 
-- La comprobación es
--    λ> quickCheck prop_reflexiva
--    +++ OK, passed 100 tests.


Soluciones en Python

from random import choice, randint, sample
from typing import TypeVar
 
from hypothesis import given
from hypothesis import strategies as st
 
from src.Relaciones_binarias import Rel, relacionArbitraria
 
A = TypeVar('A')
 
# 1ª solución
# ===========
 
def reflexiva(r: Rel[A]) -> bool:
    (us, ps) = r
    if not us:
        return True
    return (us[0], us[0]) in ps and reflexiva((us[1:], ps))
 
# 2ª solución
# ===========
 
def reflexiva2(r: Rel[A]) -> bool:
    (us, ps) = r
    return all(((x,x) in ps for x in us))
 
# 3ª solución
# ===========
 
def reflexiva3(r: Rel[A]) -> bool:
    (us, ps) = r
    for x in us:
        if (x, x) not in ps:
            return False
    return True
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.integers(min_value=0, max_value=10))
def test_reflexiva(n: int) -> None:
    r = relacionArbitraria(n)
    res = reflexiva(r)
    assert reflexiva2(r) == res
    assert reflexiva3(r) == res
 
# La comprobación es
#    > poetry run pytest -q Relaciones_reflexivas.py
#    1 passed in 0.41s
Leer más →

Universo y grafo de una relación binaria

José A. Alonso, ,

Usando el tipo de las relaciones binarias, definir las funciones

   universo :: Eq a => Rel a -> [a]
   grafo    :: Eq a => ([a],[(a,a)]) -> [(a,a)]

tales que

  • universo r es el universo de la relación r. Por ejemplo,
     λ> r = R ([1, 3],[(3, 1), (3, 3)])
     λ> universo r
     [1,3]
  • grafo r es el grafo de la relación r. Por ejemplo,
     λ> grafo r
     [(3,1),(3,3)]

Soluciones

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


Soluciones en Haskell

import Relaciones_binarias
 
universo :: Eq a => Rel a -> [a]
universo (R (u,_)) = u
 
grafo :: Eq a => Rel a -> [(a,a)]
grafo (R (_,g)) = g


Soluciones en Python

from typing import TypeVar
 
A = TypeVar('A')
 
Rel = tuple[list[A], list[tuple[A, A]]]
 
def universo(r: Rel[A]) -> list[A]:
    return r[0]
 
def grafo(r: Rel[A]) -> list[tuple[A, A]]:
    return r[1]
Leer más →

Relaciones binarias

José A. Alonso, ,

Una relación binaria R sobre un conjunto A se puede mediante un par (u,g) donde u es la lista de los elementos de tipo A (el universo de R) y g es la lista de pares de elementos de u (el grafo de R).

Definir el tipo de dato (Rel a), para representar las relaciones binarias sobre a, y la función

   esRelacionBinaria :: Eq a => Rel a -> Bool

tal que esRelacionBinaria r se verifica si r es una relación binaria. Por ejemplo,

   λ> esRelacionBinaria (R ([1, 3], [(3, 1), (3, 3)]))
   True
   λ> esRelacionBinaria (R ([1, 3], [(3, 1), (3, 2)]))
   False

Además, definir un generador de relaciones binarias y comprobar que las relaciones que genera son relaciones binarias.

Soluciones

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


Soluciones en Haskell

import Data.List (nub)
import Test.QuickCheck
 
newtype Rel a = R ([a], [(a,a)])
  deriving (Eq, Show)
 
-- 1ª solución
-- ===========
 
esRelacionBinaria :: Eq a => Rel a -> Bool
esRelacionBinaria (R (u, g)) =
  and [x `elem` u && y `elem` u | (x,y) <- g]
 
-- 2ª solución
-- ===========
 
esRelacionBinaria2 :: Eq a => Rel a -> Bool
esRelacionBinaria2 (R (u, g)) =
  all (\(x,y) -> x `elem` u && y `elem` u) g
 
-- 3ª solución
-- ===========
 
esRelacionBinaria3 :: Eq a => Rel a -> Bool
esRelacionBinaria3 (R (_, []))         = True
esRelacionBinaria3 (R (u, (x,y):g)) =
  x `elem` u &&
  y `elem` u &&
  esRelacionBinaria3 (R (u, g))
 
-- Comprobación de equivalencia
-- ============================
 
-- Generador de relaciones binarias. Por ejemplo,
--    λ> sample (relacionArbitraria :: Gen (Rel Int))
--    R ([0],[])
--    R ([0,-1,1],[(0,-1),(0,1),(-1,1),(1,0)])
--    R ([1],[])
--    R ([-5,3],[(-5,-5),(-5,3),(3,-5),(3,3)])
--    R ([-2,-7],[(-7,-7)])
--    R ([11,-7],[])
--    R ([0],[])
--    R ([-13,-11],[(-13,-13)])
relacionArbitraria :: (Arbitrary a, Eq a) => Gen (Rel a)
relacionArbitraria = do
  n <- choose (0, 10)
  u1 <- vectorOf n arbitrary
  let u = nub u1
  g <- sublistOf [(x,y) | x <- u, y <- u]
  return (R (u, g))
 
-- Relaciones es una subclase de Arbitrary.
instance (Arbitrary a, Eq a) => Arbitrary (Rel a) where
  arbitrary = relacionArbitraria
 
-- La propiedad es
prop_esRelacionBinaria :: Rel Int -> Bool
prop_esRelacionBinaria r =
  esRelacionBinaria r  &&
  esRelacionBinaria2 r &&
  esRelacionBinaria3 r
 
-- La comprobación es
--    λ> quickCheck prop_esRelacionBinaria
--    +++ OK, passed 100 tests.


Soluciones en Python

from random import choice, randint, sample
from typing import TypeVar
 
from hypothesis import given
from hypothesis import strategies as st
 
A = TypeVar('A')
 
Rel = tuple[list[A], list[tuple[A, A]]]
 
# 1ª solución
# ===========
 
def esRelacionBinaria(r: Rel[A]) -> bool:
    (u, g) = r
    return all((x in u and y in u for (x, y) in g))
 
# 2ª solución
# ===========
 
def esRelacionBinaria2(r: Rel[A]) -> bool:
    (u, g) = r
    if not g:
        return True
    (x, y) = g[0]
    return x in u and y in u and esRelacionBinaria2((u, g[1:]))
 
# 3ª solución
# ===========
 
def esRelacionBinaria3(r: Rel[A]) -> bool:
    (u, g) = r
    for (x, y) in g:
        if x not in u or y not in u:
            return False
    return True
 
# Generador de relaciones binarias
# ================================
 
# conjuntoArbitrario(n) es un conjunto arbitrario cuyos elementos están
# entre 0 y n-1. Por ejemplo,
#    >>> conjuntoArbitrario(10)
#    [8, 9, 4, 5]
#    >>> conjuntoArbitrario(10)
#    [1, 2, 3, 4, 5, 6, 7, 8, 9]
#    >>> conjuntoArbitrario(10)
#    [0, 1, 2, 3, 6, 7, 9]
#    >>> conjuntoArbitrario(10)
#    [8, 2, 3, 7]
def conjuntoArbitrario(n: int) -> list[int]:
    xs = sample(range(n), randint(0, n))
    return list(set(xs))
 
# productoCartesiano(xs, ys) es el producto cartesiano de xs e ys. Por
# ejemplo,
#    >>> productoCartesiano([2, 3], [1, 7, 5])
#    [(2, 1), (2, 7), (2, 5), (3, 1), (3, 7), (3, 5)]
def productoCartesiano(xs: list[int], ys: list[int]) -> list[tuple[int, int]]:
    return [(x, y) for x in xs for y in ys]
 
# sublistaArbitraria(xs) es una sublista arbitraria de xs. Por ejemplo,
#    >>> sublistaArbitraria(range(10))
#    [3, 7]
#    >>> sublistaArbitraria(range(10))
#    []
#    >>> sublistaArbitraria(range(10))
#    [4, 1, 0, 9, 8, 7, 5, 6, 2, 3]
def sublistaArbitraria(xs: list[A]) -> list[A]:
    n = len(xs)
    k = randint(0, n)
    return sample(xs, k)
 
# relacionArbitraria(n) es una relación arbitraria tal que los elementos
# de su universo están entre 0 y n-1. Por ejemplo,
#    >>> relacionArbitraria(3)
#    ([0, 1], [(1, 0), (1, 1)])
#    >>> relacionArbitraria(3)
#    ([], [])
#    >>> relacionArbitraria(5)
#    ([0, 2, 3, 4], [(2, 0), (3, 3), (2, 3), (4, 0), (3, 4), (4, 2)])
def relacionArbitraria(n: int) -> Rel[int]:
    u = conjuntoArbitrario(n)
    g = sublistaArbitraria(productoCartesiano(u, u))
    return (u, g)
 
# Comprobación de la propiedad
# ============================
 
# La propiedad es
@given(st.integers(min_value=0, max_value=10))
def test_esRelacionBinaria(n: int) -> None:
    r = relacionArbitraria(n)
    assert esRelacionBinaria(r)
    assert esRelacionBinaria2(r)
    assert esRelacionBinaria3(r)
 
# La comprobación es
#    > poetry run pytest -q Relaciones_binarias.py
#    1 passed in 0.14s
Leer más →

Representación matricial de relaciones binarias

José A. Alonso, ,

Dada una relación r sobre un conjunto de números enteros, la matriz asociada a r es una matriz booleana p (cuyos elementos son True o False), tal que p(i,j) = True si y sólo si i está relacionado con j mediante la relación r.

Las relaciones binarias homogéneas y las matrices booleanas se pueden representar por

   type Relacion = ([Int],[(Int,Int)])
   type Matriz = Array (Int,Int) Bool

Definir la función

   matrizRB:: Relacion -> Matriz

tal que (matrizRB r) es la matriz booleana asociada a r. Por ejemplo,

   λ> matrizRB ([1..3],[(1,1), (1,3), (3,1), (3,3)])
   array ((1,1),(3,3)) [((1,1),True) ,((1,2),False),((1,3),True),
                        ((2,1),False),((2,2),False),((2,3),False),
                        ((3,1),True) ,((3,2),False),((3,3),True)]
   λ> matrizRB ([1..3],[(1,3), (3,1)])
   array ((1,1),(3,3)) [((1,1),False),((1,2),False),((1,3),True),
                        ((2,1),False),((2,2),False),((2,3),False),
                        ((3,1),True) ,((3,2),False),((3,3),False)]
   λ> let n = 10^4 in matrizRB3 ([1..n],[(1,n),(n,1)]) ! (n,n)
   False

Soluciones

import Data.Array      (Array, accumArray, array, listArray)
import Test.QuickCheck (Arbitrary, Gen, arbitrary, sublistOf, suchThat,
                        quickCheck)
 
type Relacion = ([Int],[(Int,Int)])
type Matriz   = Array (Int,Int) Bool
 
-- 1ª solución
-- ===========
 
matrizRB1 :: Relacion -> Matriz 
matrizRB1 r = 
    array ((1,1),(n,n)) 
          [((a,b), (a,b) `elem` grafo r) | a <- [1..n], b <- [1..n]]
    where n = maximum (universo r)
          universo (us,_) = us
          grafo (_,ps)    = ps
 
-- 2ª solución
-- ===========
 
matrizRB2 :: Relacion -> Matriz
matrizRB2 r = 
    listArray ((1,1),(n,n)) 
              [(a,b) `elem` snd r | a <- [1..n], b <- [1..n]]
    where n = maximum (fst r)
 
-- 3ª solución
-- ===========
 
matrizRB3 :: Relacion -> Matriz
matrizRB3 r = 
    accumArray (||) False ((1,1),(n,n)) (zip (snd r) (repeat True))
    where n = maximum (fst r)
 
-- Comprobación de equivalencia
-- ============================
 
-- Tipo de relaciones binarias
newtype RB = RB Relacion
  deriving Show
 
-- relacionArbitraria genera una relación arbitraria. Por ejemplo, 
--    λ> generate relacionArbitraria
--    RB ([1,2,3,4,5],[(1,4),(1,5),(2,3),(2,4),(4,2),(4,3),(4,4),(5,1),(5,2),(5,3),(5,4)])
relacionArbitraria :: Gen RB
relacionArbitraria = do
  n <- arbitrary `suchThat` (> 1)
  xs <- sublistOf [(x,y) | x <- [1..n], y <- [1..n]]
  return (RB ([1..n], xs))
 
-- RB es una subclase de Arbitrary
instance Arbitrary RB where
  arbitrary = relacionArbitraria
 
-- La propiedad es
prop_matrizRB :: RB -> Bool
prop_matrizRB (RB r) =
  all (== matrizRB1 r)
      [matrizRB2 r,
       matrizRB3 r]
 
-- La comprobación es
--    λ> quickCheck prop_matrixzB
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> let n = 2000 in matrizRB1 ([1..n],[(1,n),(n,1)]) ! (n,n)
--    False
--    (2.02 secs, 1,505,248,912 bytes)
--    λ> let n = 2000 in matrizRB2 ([1..n],[(1,n),(n,1)]) ! (n,n)
--    False
--    (1.92 secs, 833,232,360 bytes)
--    λ> let n = 2000 in matrizRB3 ([1..n],[(1,n),(n,1)]) ! (n,n)
--    False
--    (0.05 secs, 32,848,696 bytes)

El código se encuentra en GitHub.

Leer más →