Menu Close

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
Inicial

6 soluciones de “Aplicaciones biyectivas

  1. angruicam1
    import Data.List (permutations,genericLength)
     
    biyectivas :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
    biyectivas xs ys
      | length xs /= length ys = []
      | otherwise              = map (zip xs) $ permutations ys
     
    nBiyectivas :: (Ord a, Ord b) => [a] -> [b] -> Integer
    nBiyectivas xs ys
      | lx /= genericLength ys = 0
      | otherwise              = product [1..lx]
        where lx = genericLength xs
    • alerodrod5

      Llego prácticamente a la misma solución pero definiendo factorial como una función aparte

      import Data.List (genericLength, permutations)
       
      biyectivas :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
      biyectivas xs ys
        | length xs == length ys = map (zip xs) (permutations ys)
        | otherwise              = []
       
      nBiyectivas :: (Ord a, Ord b) => [a] -> [b] -> Integer
      nBiyectivas xs ys
        | x ==  genericLength ys = factorial x
        | otherwise              = 0
        where x = genericLength xs
       
      factorial :: Integer -> Integer
      factorial x = product [1..x]
  2. pabhueacu
    import Data.List
     
    biyectivas  :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
    biyectivas xs ys | length xs == length ys = inyecciones xs ys
                      | otherwise = [[]]
     
    inyecciones :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
    inyecciones [] _ = [[]]
    inyecciones (x:xs) ys = concat [map ((x,y):) (inyecciones xs (delete y ys)) | y <- ys]
     
    nBiyectivas :: (Ord a, Ord b) => [a] -> [b] -> Integer
    nBiyectivas xs ys | x' == length ys = toInteger $ product [1..x'] 
                      | otherwise = 0
                              where x' =length xs
  3. menvealer

    Usando la función permutations de Data.List es mucho más sencillo. Llego a la misma definición que angruicam1 y alerodrod5.

    biyectivas :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
    biyectivas xs ys
      | length xs == length ys = map (zip xs) (permutations ys)
      | otherwise              = []
  4. rocruimon
    import Data.List
     
    biyectivas  :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
    biyectivas [] ys = []
    biyectivas xs [] = []
    biyectivas xs ys | length xs /= length ys = []
                     | otherwise = map (zip xs) (permutations ys)
     
     
     
    nBiyectivas :: (Ord a, Ord b) => [a] -> [b] -> Integer
    nBiyectivas xs ys = genericLength (biyectivas xs ys)

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.