Aplicaciones biyectivas
Definir las funciones
biyectivas :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]] nBiyectivas :: (Ord a, Ord b) => [a] -> [b] -> Integer
tales que
- (biyectivas xs ys) es el conjunto de las aplicaciones biyectivas del conjunto xs en el conjunto ys. Por ejemplo,
λ> biyectivas [1,3] [2,4] [[(1,2),(3,4)],[(1,4),(3,2)]] λ> biyectivas [1,3,5] [2,4,6] [[(1,2),(3,4),(5,6)],[(1,4),(3,2),(5,6)],[(1,6),(3,4),(5,2)], [(1,4),(3,6),(5,2)],[(1,6),(3,2),(5,4)],[(1,2),(3,6),(5,4)]] λ> biyectivas [1,3] [2,4,6] []
- (nBiyectivas xs ys) es el número de aplicaciones biyectivas del conjunto xs en el conjunto ys. Por ejemplo,
nBiyectivas [1,3] [2,4] == 2 nBiyectivas [1,3,5] [2,4,6] == 6 λ> nBiyectivas [1,3] [2,4,6] == 0 length (show (nBiyectivas2 [1..2*10^4] [1..2*10^4])) == 77338
Nota: En este ejercicio los conjuntos se representan mediante listas ordenadas de elementos distintos.
Soluciones
import Data.List (genericLength, permutations) -- 1ª definición de biyectivas biyectivas :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]] biyectivas xs ys | length xs == length ys = [zip xs zs | zs <- permutations ys] | otherwise = [] -- 1ª definición de nBiyectivas nBiyectivas :: (Ord a, Ord b) => [a] -> [b] -> Integer nBiyectivas xs ys | length xs == length ys = genericLength (biyectivas xs ys) | otherwise = 0 -- 2ª definición de nBiyectivas nBiyectivas2 :: (Ord a, Ord b) => [a] -> [b] -> Integer nBiyectivas2 xs ys | n == m = product [1..n] | otherwise = 0 where n = genericLength xs m = genericLength ys