Representación matricial de relaciones binarias
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 type Relacion = ([Int],[(Int,Int)]) type Matriz = Array (Int,Int) Bool -- 1ª definición (con array) 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ª definición (con listArray) 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ª definición (con actualización) matrizRB3 :: Relacion -> Matriz matrizRB3 r = accumArray (||) False ((1,1),(n,n)) (zip (snd r) (repeat True)) where n = maximum (fst r) -- Comparación de eficiencia: -- λ> let n = 2000 in matrizRB1 ([1..n],[(1,n),(n,1)]) ! (n,n) -- False -- (7.40 secs, 1827453320 bytes) -- λ> let n = 2000 in matrizRB2 ([1..n],[(1,n),(n,1)]) ! (n,n) -- False -- (4.80 secs, 867515144 bytes) -- λ> let n = 2000 in matrizRB3 ([1..n],[(1,n),(n,1)]) ! (n,n) -- False -- (0.09 secs, 35190408 bytes)