{"id":1897,"date":"2012-02-17T19:10:27","date_gmt":"2012-02-17T19:10:27","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1897"},"modified":"2013-03-08T05:48:55","modified_gmt":"2013-03-08T05:48:55","slug":"i1m2011-combinatoria-en-haskell-2","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-combinatoria-en-haskell-2\/","title":{"rendered":"I1M2011: Combinatoria en Haskell (2)"},"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 ejercicios 7 a 12 de la  <a href=\"https:\/\/www.glc.us.es\/~jalonso\/ejerciciosI1M2011G1\/images\/0\/0a\/Rel_17.hs\">17\u00aa relaci\u00f3n<\/a>. <\/p>\n<p> 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<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 12 primeros 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\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Definir la funci\u00f3n \r\n--    permutaciones :: [a] -> [[a]]  \r\n-- tal que (permutaciones xs) es la lista de las permutaciones de la\r\n-- lista xs. Por ejemplo,\r\n--    permutaciones \"bc\"   ==  [\"bc\",\"cb\"]\r\n--    permutaciones \"abc\"  ==  [\"abc\",\"bac\",\"bca\",\"acb\",\"cab\",\"cba\"]\r\n-- ---------------------------------------------------------------------\r\n \r\npermutaciones :: [a] -> [[a]]\r\npermutaciones []     = [[]]\r\npermutaciones (x:xs) = \r\n    concat [intercala x ys | ys <- permutaciones xs]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Definir la funci\u00f3n\r\n--    permutacionesN :: Integer -> [[Integer]]\r\n-- tal que (permutacionesN n) es la lista de las permutaciones de los n\r\n-- primeros n\u00fameros. Por ejemplo,\r\n--    ghci> permutacionesN 3\r\n--    [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]\r\n-- ---------------------------------------------------------------------  \r\n\r\npermutacionesN :: Integer -> [[Integer]]\r\npermutacionesN n = permutaciones [1..n]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9. Definir, usando permutacionesN, la funci\u00f3n\r\n--    numeroPermutacionesN :: Integer -> Integer\r\n-- tal que (numeroPermutacionesN n) es el n\u00famero de permutaciones de un\r\n-- conjunto con n elementos. Por ejemplo,\r\n--    numeroPermutacionesN 3  ==  6\r\n--    numeroPermutacionesN 4  ==  24\r\n-- ---------------------------------------------------------------------\r\n\r\nnumeroPermutacionesN :: Integer -> Integer\r\nnumeroPermutacionesN = genericLength . permutacionesN \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. Definir la funci\u00f3n\r\n--    fact :: Integer -> Integer\r\n-- tal que (fact n) es el factorial de n. Por ejemplo,\r\n--    fact 3  ==  6\r\n-- ---------------------------------------------------------------------\r\n\r\nfact :: Integer -> Integer\r\nfact n = product [1..n]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11. Definir, usando fact, la funci\u00f3n\r\n--    numeroPermutacionesN' :: Integer -> Integer\r\n-- tal que (numeroPermutacionesN' n) es el n\u00famero de permutaciones de un\r\n-- conjunto con n elementos. Por ejemplo,\r\n--    numeroPermutacionesN' 3  ==  6\r\n--    numeroPermutacionesN' 4  ==  24\r\n-- ---------------------------------------------------------------------\r\n\r\nnumeroPermutacionesN' :: Integer -> Integer\r\nnumeroPermutacionesN' = fact\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 12. Definir la funci\u00f3n\r\n--    prop_numeroPermutacionesN :: Integer -> Bool\r\n-- tal que (prop_numeroPermutacionesN n) se verifica si las funciones\r\n-- numeroPermutacionesN y numeroPermutacionesN' son equivalentes para\r\n-- los n primeros n\u00fameros. Por ejemplo,\r\n--    prop_numeroPermutacionesN 5  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nprop_numeroPermutacionesN :: Integer -> Bool\r\nprop_numeroPermutacionesN n = \r\n    and [numeroPermutacionesN x == numeroPermutacionesN' x | x <- [1..n]] \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 ejercicios 7 a 12 de la 17\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&#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":[1],"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\/1897"}],"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=1897"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1897\/revisions"}],"predecessor-version":[{"id":2850,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1897\/revisions\/2850"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1897"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1897"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1897"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}