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.

Leer más…

En la librería Data.Tree se definen los árboles y los bosques como sigue

data Tree a   = Node a (Forest a)
type Forest a = [Tree a]

Se pueden definir árboles. Por ejemplo,

ejArbol1 = Node 3 [Node 5 [Node 9 []], Node 7 []]
ejArbol2 = Node 8 [Node 4 []]

También se pueden definir bosques. Por ejemplo,

ejBosque = [ejArbol1, ejArbol2]

Se pueden dibujar los bosques con la función drawForest. Por ejemplo,

λ> putStrLn (drawForest (map (fmap show) ejBosque))
3
|
+- 5
|  |
|  `- 9
|
`- 7

8
|
`- 4

Usando la notación de los ejercicios anteriores para las subidas y bajadas en el autobús, definir la función

bosqueRecorridos :: Int -> Int -> Forest (Int,Int)

tal que (bosqueRecorridos n m) es el bosque cuyas ramas son los recorridos correctos en un autobús de capacidad n y usando m paradas. Por ejemplo,

λ> putStrLn (drawForest (map (fmap show) (bosqueRecorridos 2 3)))
(0,0)
|
+- (0,0)
|  |
|  +- (0,0)
|  |
|  +- (1,0)
|  |
|  `- (2,0)
|
+- (1,0)
|  |
|  +- (0,0)
|  |
|  +- (0,1)
|  |
|  +- (1,0)
|  |
|  `- (1,1)
|
`- (2,0)
   |
   +- (0,0)
   |
   +- (0,1)
   |
   `- (0,2)

(1,0)
|
+- (0,0)
|  |
|  +- (0,0)
|  |
|  +- (0,1)
|  |
|  +- (1,0)
|  |
|  `- (1,1)
|
+- (0,1)
|  |
|  +- (0,0)
|  |
|  +- (1,0)
|  |
|  `- (2,0)
|
+- (1,0)
|  |
|  +- (0,0)
|  |
|  +- (0,1)
|  |
|  `- (0,2)
|
`- (1,1)
   |
   +- (0,0)
   |
   +- (0,1)
   |
   +- (1,0)
   |
   `- (1,1)

(2,0)
|
+- (0,0)
|  |
|  +- (0,0)
|  |
|  +- (0,1)
|  |
|  `- (0,2)
|
+- (0,1)
|  |
|  +- (0,0)
|  |
|  +- (0,1)
|  |
|  +- (1,0)
|  |
|  `- (1,1)
|
`- (0,2)
   |
   +- (0,0)
   |
   +- (1,0)
   |
   `- (2,0)

en donde la última rama representa el recorrido [(2,0),(0,2),(2,0)].

Leer más…

Se usará la misma representación del ejercicio anterior para las subidas y bajadas en el autobús; es decir, una lista de pares donde los primeros elementos es el número de viajeros que suben y los segundo es el de los que bajan.

Un recorrido es correcto si en cada bajada tanto el número de viajeros que suben como los que bajan son positivos, el número de viajeros en el autobús no puede ser mayor que su capacidad y el número de viajeros que bajan no puede ser mayor que el número de viajeros en el autobús. Se supone que en la primera parada el autobús no tiene viajeros.

Definir la función

recorridoCorrecto :: Int -> [(Int,Int)] -> Bool

tal que (recorridoCorrecto n ps) se verifica si ps es un recorrido correcto en un autobús cuya capacidad es n. Por ejemplo,

recorridoCorrecto 20 [(3,0),(9,1),(4,10),(12,2),(6,1)]  ==  True
recorridoCorrecto 15 [(3,0),(9,1),(4,10),(12,2),(6,1)]  ==  False
recorridoCorrecto 15 [(3,2),(9,1),(4,10),(12,2),(6,1)]  ==  False
recorridoCorrecto 15 [(3,0),(2,7),(4,10),(12,2),(6,1)]  ==  False

el segundo ejemplo es incorrecto porque en la última para se supera la capacidad del autobús; el tercero, porque en la primera para no hay viajeros en el autobús que se puedan bajar y el cuarto, porque en la 2ª parada el autobús tiene 3 viajeros por lo que es imposible que se bajen 7.

Leer más…

Un autobús inicia su recorrido con 0 viajeros. El número de viajeros que se suben y bajan en cada parada se representa por un par (x,y) donde x es el número de las que suben e y el de las que bajan. Un recorrido del autobús se representa por una lista de pares representando los números de viajeros que suben o bajan en cada parada.

Definir la función

nViajerosEnBus :: [(Int, Int)] -> Int

tal que (nViajerosEnBus ps) es el número de viajeros en el autobús tras el recorrido ps. Por ejemplo,

nViajerosEnBus []                                        ==  0
nViajerosEnBus [(10,0),(3,5),(5,8)]                      ==  5
nViajerosEnBus [(3,0),(9,1),(4,10),(12,2),(6,1),(7,10)]  ==  17
nViajerosEnBus [(3,0),(9,1),(4,8),(12,2),(6,1),(7,8)]    ==  21

Leer más…

La ordenación valle de la lista [79,35,54,19,35,25,12] es la lista [79,35,25,12,19,35,54] ya que es una permutación de la primera y cumple las siguientes condiciones

• se compone de una parte decreciente ([79,35,25]), un elemento mínimo (12) y una parte creciente ([19,35,54]);
• las dos partes tienen el mismo número de elementos;
• cada elemento de la primera parte es mayor o igual que su correspondiente en la segunda parte; es decir. 79 ≥ 54, 35 ≥ 35 y 25 ≥ 19;
• además, la diferencia entre dichos elementos es la menor posible.

En el caso, de que la longitud de la lista sea par, la división tiene sólo dos partes (sin diferenciar el menor elemento). Por ejemplo, el valle de [79,35,54,19,35,25] es [79,35,25,19,35,54].

Definir la función

valle :: [Int] -> [Int]

tal que (valle xs) es la ordenación valle de la lista xs. Por ejemplo,

valle [79,35,54,19,35,25,12]       ==  [79,35,25,12,19,35,54]
valle [79,35,54,19,35,25]          ==  [79,35,25,19,35,54]
valle [67,93,100,-16,65,97,92]     ==  [100,93,67,-16,65,92,97]
valle [14,14,14,14,7,14]           ==  [14,14,14,7,14,14]
valle [14,14,14,14,14]             ==  [14,14,14,14,14]
valle [17,17,15,14,8,7,7,5,4,4,1]  ==  [17,15,8,7,4,1,4,5,7,14,17]

En el último ejemplo se muestra cómo la última condición descarta la posibilidad de que la lista [17,17,15,14,8,1,4,4,5,7,7] también sea solución ya que aunque se cumplen se cumplen las tres primeras condiciones la diferencia entre los elementos correspondientes es mayor que en la solución; por ejemplo, 17 - 7 > 17 - 17.

Leer más…

En la librería Data.Tree se definen los árboles y los bosques como sigue

data Tree a   = Node a (Forest a)
type Forest a = [Tree a]

Se pueden definir árboles. Por ejemplo,

ej = Node 3 [Node 5 [Node 9 []], Node 7 []]

Y se pueden dibujar con la función drawTree. Por ejemplo,

λ> putStrLn (drawTree (fmap show ej))
3
|
+- 5
|  |
|  `- 9
|
`- 7

Los mayores divisores de un número x son los divisores u tales que u > 1 y existe un v tal que 1 < v < u y u*v = x. Por ejemplo, los mayores divisores de 24 son 12, 8 y 6.

El árbol de los predecesores y mayores divisores de un número x es el árbol cuya raíz es x y los sucesores de cada nodo y > 1 es el conjunto formado por y-1 junto con los mayores divisores de y. Los nodos con valor 1 no tienen sucesores. Por ejemplo, el árbol de los predecesores y mayores divisores del número 6 es

    6
   / \
  5   3
  |   |
  4   2
 / \  |
3   2 1
|   |
2   1
|
1

Definir las siguientes funciones

mayoresDivisores :: Int -> [Int]
arbol            :: Int -> Tree Int
caminos          :: Int -> [[Int]]
caminosMinimales :: Int -> [[Int]]

tales que

• (mayoresDivisores x) es la lista de los mayores divisores de x. Por ejemplo,

mayoresDivisores 24  ==  [12,8,6]
mayoresDivisores 16  ==  [8,4]
mayoresDivisores 10  ==  [5]
mayoresDivisores 17  ==  []

• (arbol x) es el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

λ> putStrLn (drawTree (fmap show (arbol 6)))
6
|
+- 5
|  |
|  `- 4
|     |
|     +- 3
|     |  |
|     |  `- 2
|     |     |
|     |     `- 1
|     |
|     `- 2
|        |
|        `- 1
|
`- 3
|
`- 2
|
`- 1

• (caminos x) es la lista de los caminos en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

λ> caminos 6
[[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]

• (caminosMinimales x) es la lista de los caminos en de menor longitud en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,

λ> caminosMinimales 6
[[6,3,2,1]]
λ> caminosMinimales 17
[[17,16,4,2,1]]
λ> caminosMinimales 50
[[50,25,5,4,2,1],[50,10,9,3,2,1],[50,10,5,4,2,1]]

Leer más…

Rotar un número a la iquierda significa pasar su primer dígito al final. Por ejemplo, rotando a la izquierda el 56789 se obtiene 67895.

Las rotaciones restringidas del número 56789 se obtienen como se indica a continución:

• Se inicia con el propio número: 56789
• El anterior se rota a la izquierda y se obtiene el 67895.
• Del anterior se fija el primer dígito y se rota a la iquierda los otros. Se obtiene 68957.
• Del anterior se fijan los 2 primeros dígito y se rota a la iquierda los otros. Se obtiene 68579.
• Del anterior se fijan los 3 primeros dígito y se rota a la iquierda los otros. Se obtiene 68597.

El proceso ha terminado ya que conservando los cuatro primeros queda sólo un dígito que al girar es él mismo. Por tanto, la sucesión de las rotaciones restringidas de 56789 es

56789 -> 67895 -> 68957 -> 68579 -> 68597

y su mayor elemento es 68957.

Definir la función

maxRotaciones :: Integer -> Integer

tal que (maxRotaciones n) es el máximo de las rotaciones restringidas del número n. Por ejemplo,

maxRotaciones 56789       ==  68957
maxRotaciones 1347902468  ==  3790246814
maxRotaciones 6           ==  6
maxRotaciones 2017        ==  2017

Leer más…

Definir la función

aplicaLista :: [a -> b] -> [a] -> [b]

tal que (aplicaLista fs xs) es la lista de los valores de las funciones de fs aplicadas a los correspondientes elementos de xs. Por ejemplo,

aplicaLista [(+2),(`div` 3),(*5)] [4,6,2]    ==  [6,2,10]
aplicaLista [(+2),(`div` 3),(*5)] [4,6,2,8]  ==  [6,2,10]
aplicaLista [(>2),(==3),(<5)]     [4,6,2,9]  ==  [True,False,True]

Leer más…

Definir la función

alternadas :: String -> (String,String)

tal que (alternadas cs) es el par de cadenas (xs,ys) donde xs es la cadena obtenida escribiendo alternativamente en mayuscula o minúscula las letras de la palabra cs (que se supone que es una cadena de letras minúsculas) e ys se obtiene análogamente pero empezando en minúscula. Por ejemplo,

λ> alternadas "salamandra"
("SaLaMaNdRa","sAlAmAnDrA")
λ> alternadas "solosequenosenada"
("SoLoSeQuEnOsEnAdA","sOlOsEqUeNoSeNaDa")
λ> alternadas (replicate 30 'a')
("AaAaAaAaAaAaAaAaAaAaAaAaAaAaAa","aAaAaAaAaAaAaAaAaAaAaAaAaAaAaA")

Leer más…

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

Leer más…