{"id":1883,"date":"2012-02-15T17:55:29","date_gmt":"2012-02-15T17:55:29","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1883"},"modified":"2013-03-08T05:48:55","modified_gmt":"2013-03-08T05:48:55","slug":"i1m2011-combinatoria-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-combinatoria-en-haskell\/","title":{"rendered":"I1M2011: Combinatoria en Haskell (1)"},"content":{"rendered":"<p>En segunda parte de la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han explicado las soluciones de los 6 primeros ejercicios de la  <a href=\"https:\/\/www.glc.us.es\/~jalonso\/ejerciciosI1M2011G1\/images\/0\/0a\/Rel_16.hs\">16\u00aa relaci\u00f3n<\/a>. <\/p>\n<p> El objetivo de esta relaci\u00f3n es estudiar la generaci\u00f3n y el n\u00famero de<br \/>\nlas principales operaciones de la combinatoria. En concreto, se<br \/>\nestudia <\/p>\n<ul>\n<li> Permutaciones.\n<li> Combinaciones sin repetici\u00f3n..\n<li> Combinaciones con repetici\u00f3n\n<li> Variaciones sin repetici\u00f3n.\n<li> Variaciones con repetici\u00f3n.\n<\/ul>\n<p>Adem\u00e1s, se estudia dos temas relacionados:  <\/p>\n<ul>\n<li> Reconocimiento y generaci\u00f3n de subconjuntos y\n<li> El tri\u00e1ngulo de Pascal\n<\/ul>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Importaci\u00f3n de librer\u00edas                                           --\r\n-- ---------------------------------------------------------------------\r\n \r\nimport Test.QuickCheck\r\nimport Data.List (genericLength)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Subconjuntos\r\n-- ---------------------------------------------------------------------\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir, por recursi\u00f3n, la funci\u00f3n \r\n--    subconjunto :: Eq a => [a] -> [a] -> Bool\r\n-- tal que (subconjunto xs ys) se verifica si xs es un subconjunto de\r\n-- ys. Por ejemplo,\r\n--    subconjunto [1,3,2,3] [1,2,3]  ==  True\r\n--    subconjunto [1,3,4,3] [1,2,3]  ==  False\r\n-- ---------------------------------------------------------------------\r\n \r\nsubconjunto :: Eq a => [a] -> [a] -> Bool\r\nsubconjunto []     _ = True\r\nsubconjunto (x:xs) ys = elem x ys && subconjunto xs ys\r\n \r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir, mediante all, la funci\u00f3n \r\n--    subconjunto' :: Eq a => [a] -> [a] -> Bool\r\n-- tal que (subconjunto' xs ys) se verifica si xs es un subconjunto de\r\n-- ys. Por ejemplo,\r\n--    subconjunto' [1,3,2,3] [1,2,3]  ==  True\r\n--    subconjunto' [1,3,4,3] [1,2,3]  ==  False\r\n-- ---------------------------------------------------------------------\r\n \r\nsubconjunto' :: Eq a => [a] -> [a] -> Bool\r\nsubconjunto' xs ys = all (`elem` ys) xs\r\n \r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Comprobar con QuickCheck que las funciones subconjunto\r\n-- y subconjunto' son equivalentes.\r\n-- ---------------------------------------------------------------------\r\n \r\n-- La propiedad es\r\nprop_equivalencia :: [Int] -> [Int] -> Bool\r\nprop_equivalencia xs ys =\r\n    subconjunto xs ys == subconjunto' xs ys  \r\n \r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_equivalencia\r\n--    OK, passed 100 tests.\r\n \r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir la funci\u00f3n \r\n--    igualConjunto :: Eq a => [a] -> [a] -> Bool\r\n-- tal que (igualConjunto xs ys) se verifica si las listas xs e ys,\r\n-- vistas como conjuntos, son iguales. Por ejemplo,\r\n--    igualConjunto [1..10] [10,9..1]   ==  True\r\n--    igualConjunto [1..10] [11,10..1]  ==  False\r\n-- ---------------------------------------------------------------------\r\n \r\nigualConjunto :: Eq a => [a] -> [a] -> Bool\r\nigualConjunto xs ys = subconjunto xs ys && subconjunto ys xs\r\n \r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir la funci\u00f3n \r\n--    subconjuntos :: [a] -> [[a]]\r\n-- tal que (subconjuntos xs) es la lista de las subconjuntos de la lista\r\n-- xs. Por ejemplo, \r\n--    ghci> subconjuntos [2,3,4]\r\n--    [[2,3,4],[2,3],[2,4],[2],[3,4],[3],[4],[]]\r\n--    ghci> subconjuntos [1,2,3,4]\r\n--    [[1,2,3,4],[1,2,3],[1,2,4],[1,2],[1,3,4],[1,3],[1,4],[1],\r\n--       [2,3,4],  [2,3],  [2,4],  [2],  [3,4],  [3],  [4], []]\r\n-- ---------------------------------------------------------------------\r\n\r\nsubconjuntos :: [a] -> [[a]]\r\nsubconjuntos []     = [[]]\r\nsubconjuntos (x:xs) = [x:ys | ys <- sub] ++ sub\r\n    where sub = subconjuntos xs  \r\n\r\n-- Cambiando la comprensi\u00f3n por map se obtiene\r\nsubconjuntos' :: [a] -> [[a]]\r\nsubconjuntos' []     = [[]]\r\nsubconjuntos' (x:xs) = sub ++ map (x:) sub\r\n    where sub = subconjuntos' xs  \r\n \r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Permutaciones\r\n-- ---------------------------------------------------------------------\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir la funci\u00f3n\r\n--    intercala :: a -> [a] -> [[a]]\r\n-- tal que (intercala x ys) es la lista de las listas obtenidas\r\n-- intercalando x entre los elementos de ys. Por ejemplo,\r\n--    intercala 1 [2,3]  ==  [[1,2,3],[2,1,3],[2,3,1]]\r\n-- ---------------------------------------------------------------------\r\n\r\nintercala :: a -> [a] -> [[a]]\r\nintercala x [] = [[x]]\r\nintercala x (y:ys) = (x:y:ys) : [y:zs | zs <- intercala x ys]\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En segunda parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se han explicado las soluciones de los 6 primeros ejercicios de la 16\u00aa relaci\u00f3n. El objetivo de esta relaci\u00f3n es estudiar la generaci\u00f3n y el n\u00famero de las principales operaciones de la combinatoria. En concreto, se estudia Permutaciones. Combinaciones&#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":[186],"tags":[295],"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\/1883"}],"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=1883"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1883\/revisions"}],"predecessor-version":[{"id":2856,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1883\/revisions\/2856"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1883"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1883"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1883"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}