{"id":939,"date":"2010-12-10T08:29:25","date_gmt":"2010-12-10T08:29:25","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=939"},"modified":"2013-03-08T05:50:06","modified_gmt":"2013-03-08T05:50:06","slug":"rompecabeza-de-ullman-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/rompecabeza-de-ullman-en-haskell\/","title":{"rendered":"Rompecabeza de Ullman en Haskell"},"content":{"rendered":"<p>El problema de <a href=\"http:\/\/programmingpraxis.com\/2010\/12\/07\/ullmans-puzzle\">Programming Praxis<\/a> del 7 de diciembre de 2010 consiste en resolver el siguiente rompecabeza de Jeffrey Ullman:<\/p>\n<blockquote><p>\nDada una lista de n n\u00fameros reales, un n\u00famero real t y un n\u00famero entero k, determinar si existe un subconjunto de la lista original con k elementos tal que su suma es menor que t.\n<\/p><\/blockquote>\n<p>Por ejemplo, dada la lista de los 25 n\u00fameros 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.<\/p>\n<p>A partir de dicho problema he preparado la siguiente relaci\u00f3n de ejercicios para la asignatura de  <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-10\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a><br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\nimport Data.List\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n\r\n--    subconjuntos :: [a] -> [[a]]\r\n-- tal que (subconjuntos xs) es la lista de los subconjuntos de xs. Por \r\n-- ejemplo,\r\n--    subconjuntos \"bc\"  ==  [\"\",\"c\",\"b\",\"bc\"]\r\n--    subconjuntos \"abc\" ==  [\"\",\"c\",\"b\",\"bc\",\"a\",\"ac\",\"ab\",\"abc\"]\r\n-- ---------------------------------------------------------------------\r\n\r\nsubconjuntos :: [a] -> [[a]]\r\nsubconjuntos [] = [[]]\r\nsubconjuntos (x:xs) = zss++[x:ys | ys <- zss]\r\n    where zss = subconjuntos xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n\r\n--    subconjuntosUllman :: (Num a, Ord a) => a -> Int -> [a] -> [[a]]\r\n-- tal que (subconjuntosUllman t k xs) es la lista de los subconjuntos \r\n-- de xs con k elementos tales que su suma es menor que t. Por ejemplo,\r\n--    subconjuntosUllman 9 3 [1..10] == [[1,3,4],[1,2,5],[1,2,4],[1,2,3]]\r\n-- ---------------------------------------------------------------------\r\n\r\nsubconjuntosUllman :: (Num a, Ord a) => a -> Int -> [a] -> [[a]]\r\nsubconjuntosUllman t k xs = \r\n    [ys | ys <- subconjuntos xs, length ys == k, sum ys < t]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir la funci\u00f3n \r\n--    ullman :: (Num a, Ord a) => a -> Int -> [a] -> Bool\r\n-- tal que (ullman t k xs) se verifica si xs tiene un subconjunto con k \r\n-- elementos cuya suma sea menor que k. Por ejemplo,\r\n--    ullman 9 3 [1..10] == True\r\n--    ullman 5 3 [1..10] == False\r\n-- ---------------------------------------------------------------------\r\n\r\nullman :: (Num a, Ord a) => a -> Int -> [a] -> Bool\r\nullman t k xs = subconjuntosUllman t k xs \/= []\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Determinar la complejidad de la funci\u00f3n ullman.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La funci\u00f3n ullman es de O(n!).\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir la funci\u00f3n (de complejidad O(n log n))\r\n--    ullman2 :: (Ord a, Num a) => a -> Int -> [a] -> Bool\r\n-- tal que(ullman2 t k xs) se verifica si xs tiene un subconjunto con k \r\n-- elementos cuya suma sea menor que k. Por ejemplo,\r\n--    ullman2 9 3 [1..10] == True\r\n--    ullman2 5 3 [1..10] == False\r\n-- ---------------------------------------------------------------------\r\n\r\nullman2 :: (Ord a, Num a) => a -> Int -> [a] -> Bool\r\nullman2 t k xs = sum (take k (sort xs)) < t\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Comparar las estad\u00edsticas de calcular las siguientes\r\n-- expresiones \r\n--    ullman  9 3 [1..20]\r\n--    ullman2 9 3 [1..20]\r\n--    ullman  5 3 [1..20]\r\n--    ullman2 5 3 [1..20]\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Las estad\u00edsticas son\r\n--    *Main> ullman 9 3 [1..20]\r\n--    True\r\n--    (4.08 secs, 135267904 bytes)\r\n--    *Main> ullman2 9 3 [1..20]\r\n--    True\r\n--    (0.02 secs, 528380 bytes)\r\n--    *Main> ullman 5 3 [1..20]\r\n--    False\r\n--    (5.52 secs, 182227320 bytes)\r\n--    *Main> ullman2 5 3 [1..20]\r\n--    False\r\n--    (0.02 secs, 0 bytes)\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>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\u00fameros reales, un n\u00famero real t y un n\u00famero entero k, determinar si existe un subconjunto de la lista original con k elementos tal que su suma es menor que&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[5],"tags":[84,270],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/939"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=939"}],"version-history":[{"count":6,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/939\/revisions"}],"predecessor-version":[{"id":2967,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/939\/revisions\/2967"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=939"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=939"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=939"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}