Rompecabeza de Ullman en Haskell
El problema de Programming Praxis del 7 de diciembre de 2010 consiste en resolver el siguiente rompecabeza de Jeffrey Ullman:
Dada una lista de n números reales, un número real t y un número entero k, determinar si existe un subconjunto de la lista original con k elementos tal que su suma es menor que t.
Por ejemplo, dada la lista de los 25 números reales 18.1, 55.1, 91.2, 74.6, 73.0, 85.9, 73.9, 81.4, 87.1, 49.3, 88.8, 5.7, 26.3, 7.1, 58.2, 31.7, 5.8, 76.9, 16.5, 8.1, 48.3, 6.8, 92.4, 83.0, 19.6, t = 98.2 y k = 3, el conjunto {31.7, 16.5, 19.6} tiene 3 elementos y su suma es 67.8 que es menor que 98.2. Por tanto, el resultado es verdadero.
A partir de dicho problema he preparado la siguiente relación de ejercicios para la asignatura de Informática de 1º del Grado en Matemáticas
|
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 |
import Data.List -- --------------------------------------------------------------------- -- Ejercicio 1. Definir la función -- subconjuntos :: [a] -> [[a]] -- tal que (subconjuntos xs) es la lista de los subconjuntos de xs. Por -- ejemplo, -- subconjuntos "bc" == ["","c","b","bc"] -- subconjuntos "abc" == ["","c","b","bc","a","ac","ab","abc"] -- --------------------------------------------------------------------- subconjuntos :: [a] -> [[a]] subconjuntos [] = [[]] subconjuntos (x:xs) = zss++[x:ys | ys <- zss] where zss = subconjuntos xs -- --------------------------------------------------------------------- -- Ejercicio 2. Definir la función -- subconjuntosUllman :: (Num a, Ord a) => a -> Int -> [a] -> [[a]] -- tal que (subconjuntosUllman t k xs) es la lista de los subconjuntos -- de xs con k elementos tales que su suma es menor que t. Por ejemplo, -- subconjuntosUllman 9 3 [1..10] == [[1,3,4],[1,2,5],[1,2,4],[1,2,3]] -- --------------------------------------------------------------------- subconjuntosUllman :: (Num a, Ord a) => a -> Int -> [a] -> [[a]] subconjuntosUllman t k xs = [ys | ys <- subconjuntos xs, length ys == k, sum ys < t] -- --------------------------------------------------------------------- -- Ejercicio 3. Definir la función -- ullman :: (Num a, Ord a) => a -> Int -> [a] -> Bool -- tal que (ullman t k xs) se verifica si xs tiene un subconjunto con k -- elementos cuya suma sea menor que k. Por ejemplo, -- ullman 9 3 [1..10] == True -- ullman 5 3 [1..10] == False -- --------------------------------------------------------------------- ullman :: (Num a, Ord a) => a -> Int -> [a] -> Bool ullman t k xs = subconjuntosUllman t k xs /= [] -- --------------------------------------------------------------------- -- Ejercicio 4. Determinar la complejidad de la función ullman. -- --------------------------------------------------------------------- -- La función ullman es de O(n!). -- --------------------------------------------------------------------- -- Ejercicio 5. Definir la función (de complejidad O(n log n)) -- ullman2 :: (Ord a, Num a) => a -> Int -> [a] -> Bool -- tal que(ullman2 t k xs) se verifica si xs tiene un subconjunto con k -- elementos cuya suma sea menor que k. Por ejemplo, -- ullman2 9 3 [1..10] == True -- ullman2 5 3 [1..10] == False -- --------------------------------------------------------------------- ullman2 :: (Ord a, Num a) => a -> Int -> [a] -> Bool ullman2 t k xs = sum (take k (sort xs)) < t -- --------------------------------------------------------------------- -- Ejercicio 6. Comparar las estadísticas de calcular las siguientes -- expresiones -- ullman 9 3 [1..20] -- ullman2 9 3 [1..20] -- ullman 5 3 [1..20] -- ullman2 5 3 [1..20] -- --------------------------------------------------------------------- -- Las estadísticas son -- *Main> ullman 9 3 [1..20] -- True -- (4.08 secs, 135267904 bytes) -- *Main> ullman2 9 3 [1..20] -- True -- (0.02 secs, 528380 bytes) -- *Main> ullman 5 3 [1..20] -- False -- (5.52 secs, 182227320 bytes) -- *Main> ullman2 5 3 [1..20] -- False -- (0.02 secs, 0 bytes) |