Menu Close

Conjunto de funciones entre dos conjuntos

José A. Alonso,

Una función f entre dos conjuntos A e B se puede representar mediante una lista de pares de AxB tales que para cada elemento a de A existe un único elemento b de B tal que (a,b) pertenece a f. Por ejemplo,

  • [(1,2),(3,6)] es una función de [1,3] en [2,4,6];
  • [(1,2)] no es una función de [1,3] en [2,4,6], porque no tiene ningún par cuyo primer elemento sea igual a 3;
  • [(1,2),(3,6),(1,4)] no es una función porque hay dos pares distintos cuya primera coordenada es 1.

Definir las funciones

   funciones  :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
   nFunciones :: (Ord a, Ord b) => [a] -> [b] -> Integer

tales que

  • (funciones xs ys) es el conjunto de las funciones del conjunto xs en el conjunto ys. Por ejemplo, 
     λ> funciones [1] [2]
     [[(1,2)]]
     λ> funciones [1] [2,4]
     [[(1,2)],[(1,4)]]
     λ> funciones [1,3] [2]
     [[(1,2),(3,2)]]
     λ> funciones [1,3] [2,4]
     [[(1,2),(3,2)],[(1,2),(3,4)],[(1,4),(3,2)],[(1,4),(3,4)]]
     λ> funciones [1,3] [2,4,6]
     [[(1,2),(3,2)],[(1,2),(3,4)],[(1,2),(3,6)],
      [(1,4),(3,2)],[(1,4),(3,4)],[(1,4),(3,6)],
      [(1,6),(3,2)],[(1,6),(3,4)],[(1,6),(3,6)]]
     λ> funciones [1,3,5] [2,4]
     [[(1,2),(3,2),(5,2)],[(1,2),(3,2),(5,4)],[(1,2),(3,4),(5,2)],
      [(1,2),(3,4),(5,4)],[(1,4),(3,2),(5,2)],[(1,4),(3,2),(5,4)],
      [(1,4),(3,4),(5,2)],[(1,4),(3,4),(5,4)]]
     λ> funciones [] []
     [[]]
     λ> funciones [] [2]
     [[]]
     λ> funciones [1] []
     []
  • (nFunciones xs ys) es el número de funciones del conjunto xs en el conjunto ys. Por ejemplo, 
     nFunciones [1,3] [2,4,6]  ==  9
     nFunciones [1,3,5] [2,4]  ==  8
     length (show (nFunciones2 [1..10^6] [1..10^3]))  ==  3000001

Soluciones

import Data.List (genericLength, nub, sort, subsequences)
 
-- 1ª definición de funciones
-- ==========================
 
funciones :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
funciones xs ys =
  conjunto [r | r <- relaciones xs ys
              , esFuncion r xs ys]
 
-- (relaciones xs ys) es el conjunto de las relaciones binarias entre xs
-- e ys. Por ejemplo,
--    λ> 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 :: [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]
 
-- (esFuncional r) r se verifica si la relación r es funcional. Por
-- ejemplo, 
--    esFuncional [(2,4),(1,5),(3,4)]        ==  True
--    esFuncional [(3,4),(1,4),(1,2),(3,4)]  ==  False
esFuncional :: (Ord a, Ord b) => [(a,b)] -> Bool
esFuncional r =
  and [esUnitario (imagen r x) | x <- dominio r] 
 
-- (dominio r) es el dominio de la relación r. Por ejemplo,
--    dominio [(5,4),(1,4),(1,2),(3,4)]  ==  [1,3,5]
dominio :: Ord a => [(a,b)] -> [a]
dominio = sort . nub . map fst
 
-- (imagen r x) es la imagen de x en la relación r. Por ejemplo,
--    imagen [(5,4),(1,4),(1,2),(3,4)] 1  ==  [2,4]
--    imagen [(5,4),(1,4),(1,2),(3,4)] 2  ==  []
imagen :: (Ord a, Ord b) => [(a,b)] -> a -> [b]
imagen r x =
  conjunto [y | (x1,y) <- r, x1 == x]
 
-- (conjunto xs) es el conjunto (es decir, lista ordenada de elementos
-- distintos) correspondiente a la lista xs. Por ejemplo, 
--    conjunto [7,2,3,2,7,3]  ==  [2,3,7]
conjunto :: Ord a => [a] -> [a]
conjunto = sort . nub
 
-- (esUnitario xs) se verifica si xs tiene sólo un elemento.
esUnitario :: [a] -> Bool
esUnitario xs =
  length xs == 1
 
-- (esFuncion r xs ys) se verifica si r es una función con dominio xs y
-- codominio ys. Por ejemplo,
--    esFuncion [(2,4),(1,5),(3,4)] [1,2,3] [4,5,7]   ==  True
--    esFuncion [(2,4),(1,5),(3,4)] [1,3] [4,5,7]     ==  False
--    esFuncion [(2,4),(1,5),(3,4)] [1,2,3] [4,7]     ==  False
--    esFuncion [(1,4),(1,5),(3,4)] [1,2,3] [4,5,7]   ==  False
esFuncion :: (Ord a, Ord b) => [(a,b)] -> [a] -> [b] -> Bool
esFuncion r xs ys =
     conjunto xs == dominio r 
  && rango r `contenido` conjunto ys
  && esFuncional r
 
-- (rango r) es el rango de la relación r. Por ejemplo,
--    rango [(5,4),(1,4),(1,2),(3,4)]  ==  [2,4]
rango :: Ord b => [(a,b)] -> [b]
rango = sort . nub . map snd
 
-- (contenido xs ys) se verifica si el conjunto xs está contenido en el
-- ys. Por ejemplo,
--    [1,3] `contenido` [1,2,3,5]  ==  True
--    [1,3] `contenido` [1,2,4,5]  ==  False
contenido :: Ord a => [a] -> [a] -> Bool 
contenido xs ys =
  all (`elem` ys) xs
 
-- 2ª definición de funciones
-- ==========================
 
funciones2 :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
funciones2 xs ys =
  conjunto (aux xs ys)
  where aux [] _      = [[]]
        aux [x] ys    = [[(x,y)] | y <- ys]
        aux (x:xs) ys = [((x,y):f) | y <- ys, f <- fs]
          where fs = aux xs ys
 
-- Comparación de eficiencia de funciones
-- ======================================
 
--    λ> length (funciones [1..4] [1..4]) 
--    256
--    (2.69 secs, 754,663,072 bytes)
--    λ> length (funciones2 [1..4] [1..4]) 
--    256
--    (0.04 secs, 243,600 bytes)
 
-- 1ª definición de nFunciones
-- ===========================
 
nFunciones :: (Ord a, Ord b) => [a] -> [b] -> Integer
nFunciones xs ys =
  genericLength (funciones2 xs ys)
 
-- 2ª definición de nFunciones
-- ===========================
 
nFunciones2 :: (Ord a, Ord b) => [a] -> [b] -> Integer
nFunciones2 xs ys =
  (genericLength ys)^(genericLength xs)
 
-- Comparación de eficiencia de nFunciones
-- =======================================
 
--    λ> nFunciones [1..5] [1..5] 
--    3125
--    (1.35 secs, 1,602,872 bytes)
--    λ> nFunciones2 [1..5] [1..5] 
--    3125
--    (0.03 secs, 140,480 bytes)
Medio
, , , , , , , , ,

7 soluciones de “Conjunto de funciones entre dos conjuntos”

  1. Responder
    pabhueacu 
    import Data.List
funciones :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
funciones [] _ = [[]]
funciones _ [] = []
funciones (x:xs) ys = concat [map (z:) (funciones xs ys) | z <- (aux x ys)] 
           where aux x ys = [(x,y) | y <- ys]
 
nFunciones :: (Ord a, Ord b) => [a] -> [b] -> Integer
nFunciones xs ys = genericLength ys ^ genericLength xs
    • Responder
      jorcatote 
      import Data.List
 
funciones :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
funciones [] _ = [[]]
funciones (x:xs) ys = concat [map ((x,y):) (funciones xs ys) | y <- ys]
 
nFunciones :: (Ord a, Ord b) => [a] -> [b] -> Integer
nFunciones xs ys = genericLength ys ^ length xs

      Me ha salido esto, bastante parecida a la tuya pero creo que algo mas sencilla.

      • Responder
        jaibengue

        Usa una variable auxiliar aux, para no calcular (funciones xs ys) cada vez que vayas a añadir un elemento a la lista, quedaría así:

        import Data.List
 
funciones :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
funciones (x:xs) ys = concat [map ((x,y):) aux | y <- ys]
  where aux = funciones xs ys
funciones _ _ = [[]]
 
nFunciones :: (Ord a, Ord b) => [a] -> [b] -> Integer
nFunciones xs ys = fromIntegral(length ys ^ length xs)
 
-- Comparación de Eficiencia --
-------------------------------
 
-- λ> last (funciones [1..8] [1..8])
-- [(1,8),(2,8),(3,8),(4,8),(5,8),(6,8),(7,8),(8,8)]
-- (2.95 secs, 2,713,874,544 bytes)
 
-- λ> last (funciones2 [1..8] [1..8])
-- [(1,8),(2,8),(3,8),(4,8),(5,8),(6,8),(7,8),(8,8)]
-- (38.02 secs, 26,770,290,208 bytes)
 
-------------------------------
 
-- λ> last (show (nFunciones [1..10^6] [1..10^6]))
-- '0'
-- (0.11 secs, 156,657,288 bytes)
 
-- λ> last (show (nFunciones2 [1..10^6] [1..10^6]))
-- '0'
-- (1.73 secs, 557,986,904 bytes)
-------------------------------
  2. Responder
    alvblamol 
    import Data.List
producto :: [[a]] -> [[a]]
producto [] = [[]]
producto (xs:xss) = [x:ys | x<-xs, ys<-producto xss]
 
esFuncional :: (Ord a, Ord b) => [(a,b)] -> Bool
esFuncional xs =[fst p | p<-(nub xs)] == nub [fst p | p<-(nub xs)]
 
paresproducto :: [a] -> [a] -> [(a,a)]
paresproducto xs ys = [(head zs, last zs) | zs<-(producto [xs,ys])]
 
funciones  :: (Ord a, Ord a) => [a] -> [a] -> [[(a,a)]]
funciones xs ys = [zs | zs<-subsequences (paresproducto xs ys), esFuncional zs, length xs==length zs]
 
nFunciones :: (Ord a, Ord a) => [a] -> [a] -> Integer
nFunciones xs ys = genericLength (funciones xs ys)
    • Responder
      alvblamol

      Al igual que en las anteriores, lo mejor es cambiar la definicion de nFunciones, si no el último ejemplo no funciona:

      nFunciones :: (Ord a, Ord a) => [a] -> [a] -> Integer
nFunciones xs ys = genericLength ys ^ genericLength xs
  3. Responder
    jaibengue 
    funciones :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
funciones (x:xs) ys = aux x ys zs
  where zs = funciones xs ys
        aux a (b:bs) cs = map ((a,b):) cs ++ aux a bs cs
        aux _ _ _ = []
funciones _ _ = [[]]
 
nFunciones :: (Ord a, Ord b) => [a] -> [b] -> Integer
nFunciones xs ys = fromIntegral(length ys ^ length xs)
    • Responder
      angruicam1

      Buenas, la definición de nFunciones no es correcta. Por ejemplo:

      -- λ> length $ show $ nFunciones [1..10^6] [1..10^6]
-- 6000001
-- (3.81 secs, 654,485,896 bytes)
-- λ> length $ show $ nFunciones2 [1..10^6] [1..10^6]
-- 1
-- (0.22 secs, 144,119,688 bytes)

      Donde nFunciones2 es tu función.

Escribe tu solución

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