Conjunto de relaciones binarias entre dos conjuntos
Una relación binaria entre dos conjuntos A y B se puede representar mediante un conjunto de pares (a,b) tales que a ∈ A y b ∈ B. Por ejemplo, la relación < entre A = {1,5,3} y B = {0,2,4} se representa por {(1,2),(1,4),(3,4)}.
Definir las funciones
|
1 2 |
relaciones :: [a] -> [b] -> [[(a,b)]] nRelaciones :: [a] -> [b] -> Integer |
tales que
- (relaciones xs ys) es el conjunto de las relaciones del conjunto xs en el conjunto ys. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
λ> relaciones [1] [2] [[],[(1,2)]] λ> relaciones [1] [2,4] [[],[(1,2)],[(1,4)],[(1,2),(1,4)]] λ> relaciones [1,3] [2] [[],[(1,2)],[(3,2)],[(1,2),(3,2)]] λ> relaciones [1,3] [2,4] [[],[(1,2)],[(1,4)],[(1,2),(1,4)],[(3,2)],[(1,2),(3,2)], [(1,4),(3,2)],[(1,2),(1,4),(3,2)],[(3,4)],[(1,2),(3,4)], [(1,4),(3,4)],[(1,2),(1,4),(3,4)],[(3,2),(3,4)], [(1,2),(3,2),(3,4)],[(1,4),(3,2),(3,4)], [(1,2),(1,4),(3,2),(3,4)]] λ> relaciones [] [] [[]] λ> relaciones [] [2] [[]] λ> relaciones [1] [] [[]] |
- (nRelaciones xs ys) es el número de relaciones del conjunto xs en el conjunto ys. Por ejemplo,
|
1 2 3 |
nRelaciones [1,2] [4,5] == 16 nRelaciones [1,2] [4,5,6] == 64 nRelaciones [0..9] [0..9] == 1267650600228229401496703205376 |
Soluciones
|
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 |
import Data.List (genericLength, subsequences) relaciones :: [a] -> [b] -> [[(a,b)]] relaciones xs ys = subsequences (producto xs ys) -- (producto xs ys) es el producto cartesiano de xs e ys. Por ejemplo, -- producto [1,3] [2,4] == [(1,2),(1,4),(3,2),(3,4)] producto :: [a] -> [b] -> [(a,b)] producto xs ys = [(x,y) | x <- xs, y <- ys] -- 1ª definición de nRelaciones nRelaciones :: [a] -> [b] -> Integer nRelaciones xs ys = genericLength (relaciones xs ys) -- 2ª definición de nRelaciones nRelaciones2 :: [a] -> [b] -> Integer nRelaciones2 xs ys = 2^(length xs * length ys) -- Comparación de eficiencia -- λ> nRelaciones [1..4] [1..5] -- 1048576 -- (1.17 secs, 228,243,608 bytes) -- λ> nRelaciones2 [1..4] [1..5] -- 1048576 -- (0.02 secs, 144,856 bytes) |