{"id":3182,"date":"2013-04-04T17:54:09","date_gmt":"2013-04-04T17:54:09","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=3182"},"modified":"2013-04-05T07:55:23","modified_gmt":"2013-04-05T07:55:23","slug":"i1m201-combinatoria-en-haskell-1","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m201-combinatoria-en-haskell-1\/","title":{"rendered":"I1M2012: Combinatoria en Haskell (1)"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-12\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han explicado las soluciones de los 19 primeros ejercicios de la relaci\u00f3n 22.<\/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\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\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Combinaciones          \r\n-- ---------------------------------------------------------------------  \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 13. Definir la funci\u00f3n \r\n--    combinaciones :: Integer -> [a] -> [[a]]\r\n-- tal que (combinaciones k xs) es la lista de las combinaciones de\r\n-- orden k de los elementos de la lista xs. Por ejemplo,\r\n--    ghci> combinaciones 2 \"bcde\"\r\n--    [\"bc\",\"bd\",\"be\",\"cd\",\"ce\",\"de\"]\r\n--    ghci> combinaciones 3 \"bcde\"\r\n--    [\"bcd\",\"bce\",\"bde\",\"cde\"]\r\n--    ghci> combinaciones 3 \"abcde\"\r\n--    [\"abc\",\"abd\",\"abe\",\"acd\",\"ace\",\"ade\",\"bcd\",\"bce\",\"bde\",\"cde\"]\r\n-- ---------------------------------------------------------------------\r\n \r\n-- 1\u00aa definici\u00f3n\r\ncombinaciones_1 :: Integer -> [a] -> [[a]]\r\ncombinaciones_1 n xs = \r\n    [ys | ys <- subconjuntos xs, genericLength ys == n]  \r\n \r\n-- 2\u00aa definici\u00f3n\r\ncombinaciones_2 :: Integer -> [a] -> [[a]]\r\ncombinaciones_2 0 _          = [[]]\r\ncombinaciones_2 _ []         = []\r\ncombinaciones_2 k (x:xs) = \r\n    [x:ys | ys <- combinaciones_2 (k-1) xs] ++ combinaciones_2 k xs  \r\n\r\n-- La anterior definici\u00f3n se puede escribir usando map:\r\ncombinaciones_3 :: Integer -> [a] -> [[a]]\r\ncombinaciones_3 0 _ = [[]]\r\ncombinaciones_3 _ [] = []\r\ncombinaciones_3 (k+1) (x:xs) = \r\n    map (x:) (combinaciones_3 k xs) ++ combinaciones_3 (k+1) xs\r\n \r\n-- Nota. La segunda definici\u00f3n es m\u00e1s eficiente como se comprueba en la\r\n-- siguiente sesi\u00f3n\r\n--    ghci> :set +s\r\n--    ghci> length (combinaciones_1 2 [1..15])\r\n--    105\r\n--    (0.19 secs, 6373848 bytes)\r\n--    ghci> length (combinaciones_2 2 [1..15])\r\n--    105\r\n--    (0.01 secs, 525360 bytes)\r\n--    ghci> length (combinaciones_3 2 [1..15])\r\n--    105\r\n--    (0.02 secs, 528808 bytes)\r\n\r\n-- En lo que sigue, usaremos combinaciones como combinaciones_2\r\ncombinaciones :: Integer -> [a] -> [[a]]\r\ncombinaciones = combinaciones_2\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14. Definir la funci\u00f3n\r\n--    combinacionesN :: Integer -> Integer -> [[Int]]\r\n-- tal que (combinacionesN n k) es la lista de las combinaciones de\r\n-- orden k de los n primeros n\u00fameros. Por ejemplo,\r\n--    ghci> combinacionesN 4 2\r\n--    [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]\r\n--    ghci> combinacionesN 4 3\r\n--    [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]\r\n-- ---------------------------------------------------------------------  \r\n\r\ncombinacionesN :: Integer -> Integer -> [[Integer]]\r\ncombinacionesN n k = combinaciones k [1..n]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 15. Definir, usando combinacionesN, la funci\u00f3n\r\n--    numeroCombinaciones :: Integer -> Integer -> Integer\r\n-- tal que (numeroCombinaciones n k) es el n\u00famero de combinaciones de\r\n-- orden k de un conjunto con n elementos. Por ejemplo,\r\n--    numeroCombinaciones 4 2  ==  6\r\n--    numeroCombinaciones 4 3  ==  4\r\n-- ---------------------------------------------------------------------\r\n\r\nnumeroCombinaciones :: Integer -> Integer -> Integer\r\nnumeroCombinaciones n k = genericLength (combinacionesN n k)\r\n\r\n-- Puede definirse por composici\u00f3n\r\nnumeroCombinaciones_2 :: Integer -> Integer -> Integer\r\nnumeroCombinaciones_2 = (genericLength .) . combinacionesN\r\n\r\n-- Para facilitar la escritura de las definiciones por composici\u00f3n de\r\n-- funciones con dos argumentos, se puede definir \r\n(.:) :: (c -> d) -> (a -> b -> c) -> a -> b -> d\r\n(.:) = (.) . (.)\r\n\r\n-- con lo que la definici\u00f3n anterior se simplifica a\r\nnumeroCombinaciones_3 :: Integer -> Integer -> Integer\r\nnumeroCombinaciones_3 = genericLength .: combinacionesN\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 16. Definir la funci\u00f3n\r\n--    comb :: Integer -> Integer -> Integer\r\n-- tal que (comb n k) es el n\u00famero combinatorio n sobre k; es decir, . \r\n--    (comb n k) = n! \/ (k!(n-k)!).\r\n-- Por ejemplo,\r\n--    comb 4 2  ==  6\r\n--    comb 4 3  ==  4\r\n-- ---------------------------------------------------------------------\r\n \r\ncomb :: Integer -> Integer -> Integer\r\ncomb n k = (fact n) `div` ((fact k) * (fact (n-k)))\r\n \r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 17. Definir, usando comb, la funci\u00f3n\r\n--    numeroCombinaciones' :: Integer -> Integer -> Integer\r\n-- tal que (numeroCombinaciones' n k) es el n\u00famero de combinaciones de\r\n-- orden k de un conjunto con n elementos. Por ejemplo,\r\n--    numeroCombinaciones' 4 2  ==  6\r\n--    numeroCombinaciones' 4 3  ==  4\r\n-- ---------------------------------------------------------------------\r\n\r\nnumeroCombinaciones' :: Integer -> Integer -> Integer\r\nnumeroCombinaciones' = comb \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 18. Definir la funci\u00f3n\r\n--    prop_numeroCombinaciones :: Integer -> Bool\r\n-- tal que (prop_numeroCombinaciones n) se verifica si las funciones\r\n-- numeroCombinaciones y numeroCombinaciones' son equivalentes para\r\n-- los n primeros n\u00fameros y todo k entre 1 y n. Por ejemplo,\r\n--    prop_numeroCombinaciones 5  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nprop_numeroCombinaciones :: Integer -> Bool\r\nprop_numeroCombinaciones n =\r\n  and [numeroCombinaciones n k == numeroCombinaciones' n k | k <- [1..n]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Combinaciones con repetici\u00f3n\r\n-- ---------------------------------------------------------------------\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 19. Definir la funci\u00f3n\r\n--    combinacionesR :: Integer -> [a] -> [[a]]\r\n-- tal que (combinacionesR k xs) es la lista de las combinaciones orden\r\n-- k de los elementos de xs con repeticiones. Por ejemplo,\r\n--    ghci> combinacionesR 2 \"abc\"\r\n--    [\"aa\",\"ab\",\"ac\",\"bb\",\"bc\",\"cc\"]\r\n--    ghci> combinacionesR 3 \"bc\"\r\n--    [\"bbb\",\"bbc\",\"bcc\",\"ccc\"]\r\n--    ghci> combinacionesR 3 \"abc\"\r\n--    [\"aaa\",\"aab\",\"aac\",\"abb\",\"abc\",\"acc\",\"bbb\",\"bbc\",\"bcc\",\"ccc\"]\r\n-- ---------------------------------------------------------------------\r\n\r\ncombinacionesR :: Integer -> [a] -> [[a]]\r\ncombinacionesR _ [] = []\r\ncombinacionesR 0 _  = [[]]\r\ncombinacionesR k (x:xs) =\r\n    [x:ys | ys <- combinacionesR (k-1) (x:xs)] ++ combinacionesR k xs\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se han explicado las soluciones de los 19 primeros ejercicios de la relaci\u00f3n 22. 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 sin repetici\u00f3n.. 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":[1],"tags":[270,298],"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\/3182"}],"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=3182"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3182\/revisions"}],"predecessor-version":[{"id":3183,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3182\/revisions\/3183"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=3182"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=3182"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=3182"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}