{"id":4182,"date":"2014-03-07T17:19:12","date_gmt":"2014-03-07T16:19:12","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4182"},"modified":"2014-03-07T17:38:44","modified_gmt":"2014-03-07T16:38:44","slug":"i1m2013-combinatoria-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2013-combinatoria-en-haskell\/","title":{"rendered":"I1M2013: Combinatoria en Haskell"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-13\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han explicado las soluciones de los ejercicios de la relaci\u00f3n 21.<\/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 estudia <\/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\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 20. Definir la funci\u00f3n\r\n--    combinacionesRN :: Integer -> Integer -> [[Integer]]    \r\n-- tal que (combinacionesRN n k) es la lista de las combinaciones orden\r\n-- k de los primeros n n\u00fameros naturales. Por ejemplo,\r\n--    ghci> combinacionesRN 3 2\r\n--    [[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]]\r\n--    ghci> combinacionesRN 2 3\r\n--    [[1,1,1],[1,1,2],[1,2,2],[2,2,2]]\r\n-- ---------------------------------------------------------------------\r\n\r\ncombinacionesRN :: Integer -> Integer -> [[Integer]]    \r\ncombinacionesRN n k = combinacionesR k [1..n]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 21. Definir, usando combinacionesRN, la funci\u00f3n\r\n--    numeroCombinacionesR :: Integer -> Integer -> Integer\r\n-- tal que (numeroCombinacionesR n k) es el n\u00famero de combinaciones con\r\n-- repetici\u00f3n de orden k de un conjunto con n elementos. Por ejemplo,\r\n--    numeroCombinacionesR 3 2  ==  6\r\n--    numeroCombinacionesR 2 3  ==  4\r\n-- ---------------------------------------------------------------------\r\n\r\nnumeroCombinacionesR :: Integer -> Integer -> Integer\r\nnumeroCombinacionesR n k = genericLength (combinacionesRN n k)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 22. Definir, usando comb, la funci\u00f3n\r\n--    numeroCombinacionesR' :: Integer -> Integer -> Integer\r\n-- tal que (numeroCombinacionesR' n k) es el n\u00famero de combinaciones con\r\n-- repetici\u00f3n de orden k de un conjunto con n elementos. Por ejemplo,\r\n--    numeroCombinacionesR' 3 2  ==  6\r\n--    numeroCombinacionesR' 2 3  ==  4\r\n-- ---------------------------------------------------------------------\r\n\r\nnumeroCombinacionesR' :: Integer -> Integer -> Integer\r\nnumeroCombinacionesR' n k = comb (n+k-1) k\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 23. Definir la funci\u00f3n\r\n--    prop_numeroCombinacionesR :: Integer -> Bool\r\n-- tal que (prop_numeroCombinacionesR n) se verifica si las funciones\r\n-- numeroCombinacionesR y numeroCombinacionesR' son equivalentes para\r\n-- los n primeros n\u00fameros y todo k entre 1 y n. Por ejemplo,\r\n--    prop_numeroCombinacionesR 5  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nprop_numeroCombinacionesR :: Integer -> Bool\r\nprop_numeroCombinacionesR n =\r\n  and [numeroCombinacionesR n k == numeroCombinacionesR' n k | \r\n       k <- [1..n]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Variaciones\r\n-- ---------------------------------------------------------------------\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 24. Definir la funci\u00f3n \r\n--    variaciones :: Integer -> [a] -> [[a]]\r\n-- tal que (variaciones n xs) es la lista de las variaciones n-arias\r\n-- de la lista xs. Por ejemplo,\r\n--    variaciones 2 \"abc\"  ==  [\"ab\",\"ba\",\"ac\",\"ca\",\"bc\",\"cb\"]\r\n-- ---------------------------------------------------------------------\r\n \r\nvariaciones :: Integer -> [a] -> [[a]]\r\nvariaciones k xs = \r\n  concat (map permutaciones (combinaciones k xs))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 25. Definir la funci\u00f3n\r\n--    variacionesN :: Integer -> Integer -> [[Integer]]\r\n-- tal que (variacionesN n k) es la lista de las variaciones de orden k\r\n-- de los n primeros n\u00fameros. Por ejemplo,\r\n--    variacionesN 3 2  ==  [[1,2],[2,1],[1,3],[3,1],[2,3],[3,2]]\r\n-- ---------------------------------------------------------------------  \r\n\r\nvariacionesN :: Integer -> Integer -> [[Integer]]\r\nvariacionesN n k = variaciones k [1..n]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 26. Definir, usando variacionesN, la funci\u00f3n\r\n--    numeroVariaciones :: Integer -> Integer -> Integer\r\n-- tal que (numeroVariaciones n k) es el n\u00famero de variaciones de orden\r\n-- k de un conjunto con n elementos. Por ejemplo,\r\n--    numeroVariaciones 4 2  ==  12\r\n--    numeroVariaciones 4 3  ==  24\r\n-- ---------------------------------------------------------------------\r\n\r\nnumeroVariaciones :: Integer -> Integer -> Integer\r\nnumeroVariaciones n k = genericLength (variacionesN n k)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 27. Definir, usando product, la funci\u00f3n\r\n--    numeroVariaciones' :: Integer -> Integer -> Integer\r\n-- tal que (numeroVariaciones' n k) es el n\u00famero de variaciones de orden\r\n-- k de un conjunto con n elementos. Por ejemplo,\r\n--    numeroVariaciones' 4 2  ==  12\r\n--    numeroVariaciones' 4 3  ==  24\r\n-- ---------------------------------------------------------------------\r\n\r\nnumeroVariaciones' :: Integer -> Integer -> Integer\r\nnumeroVariaciones' n k = product [(n-k+1)..n]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 28. Definir la funci\u00f3n\r\n--    prop_numeroVariaciones :: Integer -> Bool\r\n-- tal que (prop_numeroVariaciones n) se verifica si las funciones\r\n-- numeroVariaciones y numeroVariaciones' son equivalentes para\r\n-- los n primeros n\u00fameros y todo k entre 1 y n. Por ejemplo,\r\n--    prop_numeroVariaciones 5  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nprop_numeroVariaciones :: Integer -> Bool\r\nprop_numeroVariaciones n =\r\n  and [numeroVariaciones n k == numeroVariaciones' n k | k <- [1..n]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Variaciones con repetici\u00f3n\r\n-- ---------------------------------------------------------------------\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 28. Definir la funci\u00f3n\r\n--    variacionesR :: Integer -> [a] -> [[a]]\r\n-- tal que (variacionesR k xs) es la lista de las variaciones de orden\r\n-- k de los elementos de xs con repeticiones. Por ejemplo,\r\n--    ghci> variacionesR 1 \"ab\"\r\n--    [\"a\",\"b\"]\r\n--    ghci> variacionesR 2 \"ab\"\r\n--    [\"aa\",\"ab\",\"ba\",\"bb\"]\r\n--    ghci> variacionesR 3 \"ab\"\r\n--    [\"aaa\",\"aab\",\"aba\",\"abb\",\"baa\",\"bab\",\"bba\",\"bbb\"]\r\n-- ---------------------------------------------------------------------\r\n\r\nvariacionesR :: Integer -> [a] -> [[a]]\r\nvariacionesR _ [] = [[]]\r\nvariacionesR 0 _  = [[]] \r\nvariacionesR k xs =\r\n    [z:ys | z <- xs, ys <- variacionesR (k-1) xs]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 30. Definir la funci\u00f3n\r\n--    variacionesRN :: Integer -> Integer -> [[Integer]]    \r\n-- tal que (variacionesRN n k) es la lista de las variaciones orden\r\n-- k de los primeros n n\u00fameros naturales. Por ejemplo,\r\n--    ghci> variacionesRN 3 2\r\n--    [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]\r\n--    ghci> variacionesRN 2 3\r\n--    [[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,1],[2,1,2],[2,2,1],[2,2,2]]\r\n-- ---------------------------------------------------------------------\r\n\r\nvariacionesRN :: Integer -> Integer -> [[Integer]]    \r\nvariacionesRN n k = variacionesR k [1..n]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 31. Definir, usando variacionesR, la funci\u00f3n\r\n--    numeroVariacionesR :: Integer -> Integer -> Integer\r\n-- tal que (numeroVariacionesR n k) es el n\u00famero de variaciones con\r\n-- repetici\u00f3n de orden k de un conjunto con n elementos. Por ejemplo,\r\n--    numeroVariacionesR 3 2  ==  9\r\n--    numeroVariacionesR 2 3  ==  8\r\n-- ---------------------------------------------------------------------\r\n\r\nnumeroVariacionesR :: Integer -> Integer -> Integer\r\nnumeroVariacionesR n k = genericLength (variacionesRN n k)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 32. Definir, usando (^), la funci\u00f3n\r\n--    numeroVariacionesR' :: Integer -> Integer -> Integer\r\n-- tal que (numeroVariacionesR' n k) es el n\u00famero de variaciones con\r\n-- repetici\u00f3n de orden k de un conjunto con n elementos. Por ejemplo,\r\n--    numeroVariacionesR' 3 2  ==  9\r\n--    numeroVariacionesR' 2 3  ==  8\r\n-- ---------------------------------------------------------------------\r\n\r\nnumeroVariacionesR' :: Integer -> Integer -> Integer\r\nnumeroVariacionesR' n k = n^k\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 33. Definir la funci\u00f3n\r\n--    prop_numeroVariacionesR :: Integer -> Bool\r\n-- tal que (prop_numeroVariacionesR n) se verifica si las funciones\r\n-- numeroVariacionesR y numeroVariacionesR' son equivalentes para\r\n-- los n primeros n\u00fameros y todo k entre 1 y n. Por ejemplo,\r\n--    prop_numeroVariacionesR 5  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nprop_numeroVariacionesR :: Integer -> Bool\r\nprop_numeroVariacionesR n =\r\n  and [numeroVariacionesR n k == numeroVariacionesR' n k | \r\n       k <- [1..n]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 El tri\u00e1ngulo de Pascal\r\n-- ---------------------------------------------------------------------\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 34.1. El tri\u00e1ngulo de Pascal es un tri\u00e1ngulo de n\u00fameros\r\n--          1\r\n--         1 1\r\n--        1 2 1\r\n--      1  3 3  1\r\n--     1 4  6  4 1\r\n--    1 5 10 10 5 1\r\n--   ...............\r\n-- construido de la siguiente forma\r\n-- * la primera fila est\u00e1 formada por el n\u00famero 1;\r\n-- * las filas siguientes se construyen sumando los n\u00fameros adyacentes\r\n--   de la fila superior y a\u00f1adiendo un 1 al principio y al final de la\r\n--   fila. \r\n-- \r\n-- Definir la funci\u00f3n \r\n--    pascal :: Integer -> [Integer]\r\n-- tal que (pascal n) es la n-\u00e9sima fila del tri\u00e1ngulo de Pascal. Por\r\n-- ejemplo, \r\n--    pascal 6  ==  [1,5,10,10,5,1]  \r\n-- ----------------------------------------------------------------------------\r\n \r\npascal :: Integer -> [Integer]\r\npascal 1 = [1]\r\npascal n = [1] ++ [x+y | (x,y) <- pares (pascal (n-1))] ++ [1]\r\n \r\n-- (pares xs) es la lista formada por los pares de elementos adyacentes\r\n-- de la lista xs. Por ejemplo, \r\n--    pares [1,4,6,4,1]  ==  [(1,4),(4,6),(6,4),(4,1)]  \r\npares :: [a] -> [(a,a)]\r\npares (x:y:xs) = (x,y) : pares (y:xs)\r\npares _        = []  \r\n \r\n-- otra definici\u00f3n de pares, usando zip, es\r\npares' :: [a] -> [(a,a)]\r\npares' xs = zip xs (tail xs)\r\n \r\n-- las definiciones son equivalentes\r\nprop_pares :: [Integer] -> Bool\r\nprop_pares xs =\r\n    pares xs == pares' xs  \r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_pares\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 34.2. Comprobar con QuickCheck, que la fila n-\u00e9sima del\r\n-- tri\u00e1ngulo de Pascal tiene n elementos.\r\n-- ---------------------------------------------------------------------\r\n \r\n-- La propiedad es\r\nprop_Pascal :: Integer -> Property\r\nprop_Pascal n =\r\n    n >= 1 ==> genericLength (pascal n) == n\r\n \r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_Pascal\r\n--    OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 34.3. Comprobar con QuickCheck, que la suma de los\r\n-- elementos de la fila n-\u00e9sima del tri\u00e1ngulo de Pascal es igual a\r\n-- 2^(n-1). \r\n-- ---------------------------------------------------------------------\r\n \r\n-- la propiedad es\r\nprop_sumaPascal :: Integer -> Property\r\nprop_sumaPascal n =\r\n    n >= 1 ==> sum (pascal n) == 2^(n-1)\r\n \r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_sumaPascal\r\n--    OK, passed 100 tests.\r\n \r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 34.4. Comprobar con QuickCheck, que el m-\u00e9simo elemento de\r\n-- la fila (n+1)-\u00e9sima del tri\u00e1ngulo de Pascal es el n\u00famero combinatorio \r\n-- (comb n m).\r\n-- ---------------------------------------------------------------------\r\n \r\n--  La propiedad es\r\nprop_Combinaciones :: Integer -> Property\r\nprop_Combinaciones n =\r\n    n >= 1 ==> pascal n == [comb (n-1) m | m <- [0..n-1]]\r\n \r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_Combinaciones\r\n--    OK, passed 100 tests.\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 ejercicios de la relaci\u00f3n 21. 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 con repetici\u00f3n&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","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":[222],"tags":[270,300,194,126],"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\/4182"}],"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=4182"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4182\/revisions"}],"predecessor-version":[{"id":4185,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4182\/revisions\/4185"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4182"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4182"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4182"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}