Conjunto de funciones entre dos conjuntos
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
|
1 2 |
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,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
λ> 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,
|
1 2 3 |
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
|
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
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) |