{"id":5944,"date":"2018-02-21T19:53:16","date_gmt":"2018-02-21T18:53:16","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5944"},"modified":"2018-02-24T19:54:24","modified_gmt":"2018-02-24T18:54:24","slug":"i1m2017-combinatoria-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2017-combinatoria-en-haskell\/","title":{"rendered":"I1M2017: Combinatoria en Haskell"},"content":{"rendered":"<p>En la primera parte de la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-17\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han explicado las soluciones de los ejercicios de la relaci\u00f3n 24 cuyo objetivo 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.<\/li>\n<li>Combinaciones sin repetici\u00f3n.          <\/li>\n<li>Combinaciones con repetici\u00f3n<\/li>\n<li>Variaciones sin repetici\u00f3n.<\/li>\n<li>Variaciones con repetici\u00f3n.<\/li>\n<\/ul>\n<p>En la segunda parte se han resuelto algunos de los problemas de la relaci\u00f3n anterior usando la librer\u00eda <a href=\"http:\/\/bit.ly\/2ESN4VT\">Math.Combinat.Sets<\/a> y se han comparado las definiciones de las funciones de la librer\u00eda con las presentadas en la primera parte.<\/p>\n<p>Los ejercicios, y sus soluciones, de la primera parte se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- El objetivo de esta relaci\u00f3n es estudiar la generaci\u00f3n y el n\u00famero de\n-- las principales operaciones de la combinatoria. En concreto, se\n-- estudia \n--    * Permutaciones.\n--    * Combinaciones sin repetici\u00f3n.          \n--    * Combinaciones con repetici\u00f3n\n--    * Variaciones sin repetici\u00f3n.\n--    * Variaciones con repetici\u00f3n.\n-- Como referencia se puede usar los apuntes de http:\/\/bit.ly\/2HyyxAi\n\n-- ---------------------------------------------------------------------\n-- Importaci\u00f3n de librer\u00edas                                           --\n-- ---------------------------------------------------------------------\n \nimport Test.QuickCheck\nimport Data.List (genericLength)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir, por recursi\u00f3n, la funci\u00f3n \n--    subconjunto :: Eq a => [a] -> [a] -> Bool\n-- tal que (subconjunto xs ys) se verifica si xs es un subconjunto de\n-- ys. Por ejemplo,\n--    subconjunto [1,3,2,3] [1,2,3]  ==  True\n--    subconjunto [1,3,4,3] [1,2,3]  ==  False\n-- ---------------------------------------------------------------------\n \nsubconjunto :: Eq a => [a] -> [a] -> Bool\nsubconjunto []     _ = True\nsubconjunto (x:xs) ys = elem x ys && subconjunto xs ys\n\n-- Definici\u00f3n por plegado\nsubconjunto2 :: Eq a => [a] -> [a] -> Bool\nsubconjunto2 xs ys = foldr f True xs \n  where f x z = x `elem` ys && z \n\n-- La propiedad de equivalencia es\nprop_equiv_subconjunto :: [Int] -> [Int] -> Bool\nprop_equiv_subconjunto xs ys =\n  subconjunto xs ys == subconjunto2 xs ys\n\n-- La comprobaci\u00f3n es\n--    prop_equiv_subconjunto :: [Int] -> [Int] -> Bool\n--    prop_equiv_subconjunto xs ys =\n--      subconjunto xs ys == subconjunto2 xs ys\n  \n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir, mediante all, la funci\u00f3n \n--    subconjunto' :: Eq a => [a] -> [a] -> Bool\n-- tal que (subconjunto' xs ys) se verifica si xs es un subconjunto de\n-- ys. Por ejemplo,\n--    subconjunto' [1,3,2,3] [1,2,3]  ==  True\n--    subconjunto' [1,3,4,3] [1,2,3]  ==  False\n-- ---------------------------------------------------------------------\n \nsubconjunto' :: Eq a => [a] -> [a] -> Bool\nsubconjunto' xs ys = all (`elem` ys) xs\n \n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Comprobar con QuickCheck que las funciones subconjunto\n-- y subconjunto' son equivalentes.\n-- ---------------------------------------------------------------------\n \n-- La propiedad es\nprop_equivalencia :: [Int] -> [Int] -> Bool\nprop_equivalencia xs ys =\n  subconjunto xs ys == subconjunto' xs ys  \n \n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_equivalencia\n--    OK, passed 100 tests.\n  \n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n \n--    igualConjunto :: Eq a => [a] -> [a] -> Bool\n-- tal que (igualConjunto xs ys) se verifica si las listas xs e ys,\n-- vistas como conjuntos, son iguales. Por ejemplo,\n--    igualConjunto [1..10] [10,9..1]   ==  True\n--    igualConjunto [1..10] [11,10..1]  ==  False\n-- ---------------------------------------------------------------------\n \nigualConjunto :: Eq a => [a] -> [a] -> Bool\nigualConjunto xs ys = subconjunto xs ys && subconjunto ys xs\n \n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n \n--    subconjuntos :: [a] -> [[a]]\n-- tal que (subconjuntos xs) es la lista de las subconjuntos de la lista\n-- xs. Por ejemplo, \n--    ghci> subconjuntos [2,3,4]\n--    [[2,3,4],[2,3],[2,4],[2],[3,4],[3],[4],[]]\n--    ghci> subconjuntos [1,2,3,4]\n--    [[1,2,3,4],[1,2,3],[1,2,4],[1,2],[1,3,4],[1,3],[1,4],[1],\n--       [2,3,4],  [2,3],  [2,4],  [2],  [3,4],  [3],  [4], []]\n-- ---------------------------------------------------------------------\n\nsubconjuntos :: [a] -> [[a]]\nsubconjuntos []     = [[]]\nsubconjuntos (x:xs) = [x:ys | ys <- sub] ++ sub\n    where sub = subconjuntos xs  \n\n-- Cambiando la comprensi\u00f3n por map se obtiene\nsubconjuntos' :: [a] -> [[a]]\nsubconjuntos' []     = [[]]\nsubconjuntos' (x:xs) = sub ++ map (x:) sub\n    where sub = subconjuntos' xs  \n \n-- ---------------------------------------------------------------------\n-- \u00a7 Permutaciones\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Definir la funci\u00f3n\n--    intercala :: a -> [a] -> [[a]]\n-- tal que (intercala x ys) es la lista de las listas obtenidas\n-- intercalando x entre los elementos de ys. Por ejemplo,\n--    intercala 1 [2,3]  ==  [[1,2,3],[2,1,3],[2,3,1]]\n-- ---------------------------------------------------------------------\n\n-- Una definici\u00f3n recursiva es\nintercala1 :: a -> [a] -> [[a]]\nintercala1 x []     = [[x]]\nintercala1 x (y:ys) = (x:y:ys) : [y:zs | zs <- intercala1 x ys]\n\n-- Otra definici\u00f3n, m\u00e1s eficiente, es\nintercala :: a -> [a] -> [[a]]\nintercala y xs = \n  [take n xs ++ (y : drop n xs) | n <- [0..length xs]]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Definir la funci\u00f3n \n--    permutaciones :: [a] -> [[a]]  \n-- tal que (permutaciones xs) es la lista de las permutaciones de la\n-- lista xs. Por ejemplo,\n--    permutaciones \"bc\"   ==  [\"bc\",\"cb\"]\n--    permutaciones \"abc\"  ==  [\"abc\",\"bac\",\"bca\",\"acb\",\"cab\",\"cba\"]\n-- ---------------------------------------------------------------------\n \npermutaciones :: [a] -> [[a]]\npermutaciones []     = [[]]\npermutaciones (x:xs) = \n  concat [intercala x ys | ys <- permutaciones xs]\n\n-- 2\u00aa definici\u00f3n\npermutaciones2 :: [a] -> [[a]]\npermutaciones2 []     = [[]]\npermutaciones2 (x:xs) = concatMap (intercala x) (permutaciones2 xs) \n\n-- 3\u00aa definici\u00f3n\npermutaciones3 :: [a] -> [[a]]\npermutaciones3 = foldr (concatMap . intercala) [[]]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Definir la funci\u00f3n\n--    permutacionesN :: Int -> [[Int]]\n-- tal que (permutacionesN n) es la lista de las permutaciones de los n\n-- primeros n\u00fameros. Por ejemplo,\n--    ghci> permutacionesN 3\n--    [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]\n-- ---------------------------------------------------------------------  \n\n-- 1\u00aa definici\u00f3n\npermutacionesN :: Int -> [[Int]]\npermutacionesN n = permutaciones [1..n]\n\n-- 2\u00aa definici\u00f3n\npermutacionesN2 :: Int -> [[Int]]\npermutacionesN2 = permutaciones . enumFromTo 1\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Definir, usando permutacionesN, la funci\u00f3n\n--    numeroPermutacionesN :: Int -> Int\n-- tal que (numeroPermutacionesN n) es el n\u00famero de permutaciones de un\n-- conjunto con n elementos. Por ejemplo,\n--    numeroPermutacionesN 3  ==  6\n--    numeroPermutacionesN 4  ==  24\n-- ---------------------------------------------------------------------\n\nnumeroPermutacionesN :: Int -> Int\nnumeroPermutacionesN = genericLength . permutacionesN \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10. Definir la funci\u00f3n\n--    fact :: Int -> Int\n-- tal que (fact n) es el factorial de n. Por ejemplo,\n--    fact 3  ==  6\n-- ---------------------------------------------------------------------\n\nfact :: Int -> Int\nfact n = product [1..n]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11. Definir, usando fact, la funci\u00f3n\n--    numeroPermutacionesN' :: Int -> Int\n-- tal que (numeroPermutacionesN' n) es el n\u00famero de permutaciones de un\n-- conjunto con n elementos. Por ejemplo,\n--    numeroPermutacionesN' 3  ==  6\n--    numeroPermutacionesN' 4  ==  24\n-- ---------------------------------------------------------------------\n\nnumeroPermutacionesN' :: Int -> Int\nnumeroPermutacionesN' = fact\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 12. Definir la funci\u00f3n\n--    prop_numeroPermutacionesN :: Int -> Bool\n-- tal que (prop_numeroPermutacionesN n) se verifica si las funciones\n-- numeroPermutacionesN y numeroPermutacionesN' son equivalentes para\n-- los n primeros n\u00fameros. Por ejemplo,\n--    prop_numeroPermutacionesN 5  ==  True\n-- ---------------------------------------------------------------------\n\nprop_numeroPermutacionesN :: Int -> Bool\nprop_numeroPermutacionesN n = \n    and [numeroPermutacionesN x == numeroPermutacionesN' x | x <- [1..n]] \n\n-- ---------------------------------------------------------------------\n-- \u00a7 Combinaciones          \n-- ---------------------------------------------------------------------  \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13. Definir la funci\u00f3n \n--    combinaciones :: Int -> [a] -> [[a]]\n-- tal que (combinaciones k xs) es la lista de las combinaciones de\n-- orden k de los elementos de la lista xs. Por ejemplo,\n--    ghci> combinaciones 2 \"bcde\"\n--    [\"bc\",\"bd\",\"be\",\"cd\",\"ce\",\"de\"]\n--    ghci> combinaciones 3 \"bcde\"\n--    [\"bcd\",\"bce\",\"bde\",\"cde\"]\n--    ghci> combinaciones 3 \"abcde\"\n--    [\"abc\",\"abd\",\"abe\",\"acd\",\"ace\",\"ade\",\"bcd\",\"bce\",\"bde\",\"cde\"]\n-- ---------------------------------------------------------------------\n \n-- 1\u00aa definici\u00f3n\ncombinaciones1 :: Int -> [a] -> [[a]]\ncombinaciones1 n xs = \n    [ys | ys <- subconjuntos xs, genericLength ys == n]  \n \n-- 2\u00aa definici\u00f3n\ncombinaciones2 :: Int -> [a] -> [[a]]\ncombinaciones2 0 _          = [[]]\ncombinaciones2 _ []         = []\ncombinaciones2 k (x:xs) = \n    [x:ys | ys <- combinaciones2 (k-1) xs] ++ combinaciones2 k xs  \n\n-- La anterior definici\u00f3n se puede escribir usando map:\ncombinaciones3 :: Int -> [a] -> [[a]]\ncombinaciones3 0 _      = [[]]\ncombinaciones3 _ []     = []\ncombinaciones3 k (x:xs) = \n    map (x:) (combinaciones3 (k-1) xs) ++ combinaciones3 k xs\n \n-- Nota. La segunda definici\u00f3n es m\u00e1s eficiente como se comprueba en la\n-- siguiente sesi\u00f3n\n--    ghci> :set +s\n--    ghci> length (combinaciones1 2 [1..15])\n--    105\n--    (0.19 secs, 6373848 bytes)\n--    ghci> length (combinaciones2 2 [1..15])\n--    105\n--    (0.01 secs, 525360 bytes)\n--    ghci> length (combinaciones3 2 [1..15])\n--    105\n--    (0.02 secs, 528808 bytes)\n\n-- En lo que sigue, usaremos combinaciones como combinaciones2\ncombinaciones :: Int -> [a] -> [[a]]\ncombinaciones = combinaciones2\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 14. Definir la funci\u00f3n\n--    combinacionesN :: Int -> Int -> [[Int]]\n-- tal que (combinacionesN n k) es la lista de las combinaciones de\n-- orden k de los n primeros n\u00fameros. Por ejemplo,\n--    ghci> combinacionesN 4 2\n--    [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]\n--    ghci> combinacionesN 4 3\n--    [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]\n-- ---------------------------------------------------------------------  \n\n-- 1\u00aa definici\u00f3n\ncombinacionesN :: Int -> Int -> [[Int]]\ncombinacionesN n k = combinaciones k [1..n]\n\n-- 2\u00aa definici\u00f3n\ncombinacionesN2 :: Int -> Int -> [[Int]]\ncombinacionesN2 = flip combinaciones . enumFromTo 1\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 15. Definir, usando combinacionesN, la funci\u00f3n\n--    numeroCombinaciones :: Int -> Int -> Int\n-- tal que (numeroCombinaciones n k) es el n\u00famero de combinaciones de\n-- orden k de un conjunto con n elementos. Por ejemplo,\n--    numeroCombinaciones 4 2  ==  6\n--    numeroCombinaciones 4 3  ==  4\n-- ---------------------------------------------------------------------\n\nnumeroCombinaciones :: Int -> Int -> Int\nnumeroCombinaciones n k = genericLength (combinacionesN n k)\n\n-- Puede definirse por composici\u00f3n\nnumeroCombinaciones2 :: Int -> Int -> Int\nnumeroCombinaciones2 = (genericLength .) . combinacionesN\n\n-- Para facilitar la escritura de las definiciones por composici\u00f3n de\n-- funciones con dos argumentos, se puede definir \n(.:) :: (c -> d) -> (a -> b -> c) -> a -> b -> d\n(.:) = (.) . (.)\n\n-- con lo que la definici\u00f3n anterior se simplifica a\nnumeroCombinaciones3 :: Int -> Int -> Int\nnumeroCombinaciones3 = genericLength .: combinacionesN\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 16. Definir la funci\u00f3n\n--    comb :: Int -> Int -> Int\n-- tal que (comb n k) es el n\u00famero combinatorio n sobre k; es decir, . \n--    (comb n k) = n! \/ (k!(n-k)!).\n-- Por ejemplo,\n--    comb 4 2  ==  6\n--    comb 4 3  ==  4\n-- ---------------------------------------------------------------------\n \ncomb :: Int -> Int -> Int\ncomb n k = fact n `div` (fact k * fact (n-k))\n \n-- ---------------------------------------------------------------------\n-- Ejercicio 17. Definir, usando comb, la funci\u00f3n\n--    numeroCombinaciones' :: Int -> Int -> Int\n-- tal que (numeroCombinaciones' n k) es el n\u00famero de combinaciones de\n-- orden k de un conjunto con n elementos. Por ejemplo,\n--    numeroCombinaciones' 4 2  ==  6\n--    numeroCombinaciones' 4 3  ==  4\n-- ---------------------------------------------------------------------\n\nnumeroCombinaciones' :: Int -> Int -> Int\nnumeroCombinaciones' = comb \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 18. Definir la funci\u00f3n\n--    prop_numeroCombinaciones :: Int -> Bool\n-- tal que (prop_numeroCombinaciones n) se verifica si las funciones\n-- numeroCombinaciones y numeroCombinaciones' son equivalentes para\n-- los n primeros n\u00fameros y todo k entre 1 y n. Por ejemplo,\n--    prop_numeroCombinaciones 5  ==  True\n-- ---------------------------------------------------------------------\n\nprop_numeroCombinaciones :: Int -> Bool\nprop_numeroCombinaciones n =\n  and [numeroCombinaciones n k == numeroCombinaciones' n k | k <- [1..n]]\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Combinaciones con repetici\u00f3n\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 19. Definir la funci\u00f3n\n--    combinacionesR :: Int -> [a] -> [[a]]\n-- tal que (combinacionesR k xs) es la lista de las combinaciones orden\n-- k de los elementos de xs con repeticiones. Por ejemplo,\n--    ghci> combinacionesR 2 \"abc\"\n--    [\"aa\",\"ab\",\"ac\",\"bb\",\"bc\",\"cc\"]\n--    ghci> combinacionesR 3 \"bc\"\n--    [\"bbb\",\"bbc\",\"bcc\",\"ccc\"]\n--    ghci> combinacionesR 3 \"abc\"\n--    [\"aaa\",\"aab\",\"aac\",\"abb\",\"abc\",\"acc\",\"bbb\",\"bbc\",\"bcc\",\"ccc\"]\n-- ---------------------------------------------------------------------\n\ncombinacionesR :: Int -> [a] -> [[a]]\ncombinacionesR _ [] = []\ncombinacionesR 0 _  = [[]]\ncombinacionesR k (x:xs) =\n    [x:ys | ys <- combinacionesR (k-1) (x:xs)] ++ combinacionesR k xs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 20. Definir la funci\u00f3n\n--    combinacionesRN :: Int -> Int -> [[Int]]    \n-- tal que (combinacionesRN n k) es la lista de las combinaciones orden\n-- k de los primeros n n\u00fameros naturales. Por ejemplo,\n--    ghci> combinacionesRN 3 2\n--    [[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]]\n--    ghci> combinacionesRN 2 3\n--    [[1,1,1],[1,1,2],[1,2,2],[2,2,2]]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n\ncombinacionesRN :: Int -> Int -> [[Int]]    \ncombinacionesRN n k = combinacionesR k [1..n]\n\n-- 2\u00aa definici\u00f3n\ncombinacionesRN2 :: Int -> Int -> [[Int]]    \ncombinacionesRN2 = flip combinacionesR . enumFromTo 1\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 21. Definir, usando combinacionesRN, la funci\u00f3n\n--    numeroCombinacionesR :: Int -> Int -> Int\n-- tal que (numeroCombinacionesR n k) es el n\u00famero de combinaciones con\n-- repetici\u00f3n de orden k de un conjunto con n elementos. Por ejemplo,\n--    numeroCombinacionesR 3 2  ==  6\n--    numeroCombinacionesR 2 3  ==  4\n-- ---------------------------------------------------------------------\n\nnumeroCombinacionesR :: Int -> Int -> Int\nnumeroCombinacionesR n k = genericLength (combinacionesRN n k)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 22. Definir, usando comb, la funci\u00f3n\n--    numeroCombinacionesR' :: Int -> Int -> Int\n-- tal que (numeroCombinacionesR' n k) es el n\u00famero de combinaciones con\n-- repetici\u00f3n de orden k de un conjunto con n elementos. Por ejemplo,\n--    numeroCombinacionesR' 3 2  ==  6\n--    numeroCombinacionesR' 2 3  ==  4\n-- ---------------------------------------------------------------------\n\nnumeroCombinacionesR' :: Int -> Int -> Int\nnumeroCombinacionesR' n k = comb (n+k-1) k\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 23. Definir la funci\u00f3n\n--    prop_numeroCombinacionesR :: Int -> Bool\n-- tal que (prop_numeroCombinacionesR n) se verifica si las funciones\n-- numeroCombinacionesR y numeroCombinacionesR' son equivalentes para\n-- los n primeros n\u00fameros y todo k entre 1 y n. Por ejemplo,\n--    prop_numeroCombinacionesR 5  ==  True\n-- ---------------------------------------------------------------------\n\nprop_numeroCombinacionesR :: Int -> Bool\nprop_numeroCombinacionesR n =\n  and [numeroCombinacionesR n k == numeroCombinacionesR' n k | \n       k <- [1..n]]\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Variaciones\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 24. Definir la funci\u00f3n \n--    variaciones :: Int -> [a] -> [[a]]\n-- tal que (variaciones n xs) es la lista de las variaciones n-arias\n-- de la lista xs. Por ejemplo,\n--    variaciones 2 \"abc\"  ==  [\"ab\",\"ba\",\"ac\",\"ca\",\"bc\",\"cb\"]\n-- ---------------------------------------------------------------------\n \nvariaciones :: Int -> [a] -> [[a]]\nvariaciones k xs = concatMap permutaciones (combinaciones k xs)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 25. Definir la funci\u00f3n\n--    variacionesN :: Int -> Int -> [[Int]]\n-- tal que (variacionesN n k) es la lista de las variaciones de orden k\n-- de los n primeros n\u00fameros. Por ejemplo,\n--    variacionesN 3 2  ==  [[1,2],[2,1],[1,3],[3,1],[2,3],[3,2]]\n-- ---------------------------------------------------------------------  \n\nvariacionesN :: Int -> Int -> [[Int]]\nvariacionesN n k = variaciones k [1..n]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 26. Definir, usando variacionesN, la funci\u00f3n\n--    numeroVariaciones :: Int -> Int -> Int\n-- tal que (numeroVariaciones n k) es el n\u00famero de variaciones de orden\n-- k de un conjunto con n elementos. Por ejemplo,\n--    numeroVariaciones 4 2  ==  12\n--    numeroVariaciones 4 3  ==  24\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n\nnumeroVariaciones :: Int -> Int -> Int\nnumeroVariaciones n k = genericLength (variacionesN n k)\n\n-- 2\u00aa definici\u00f3n\nnumeroVariaciones2 :: Int -> Int -> Int\nnumeroVariaciones2 = (genericLength .) . variacionesN\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 27. Definir, usando product, la funci\u00f3n\n--    numeroVariaciones' :: Int -> Int -> Int\n-- tal que (numeroVariaciones' n k) es el n\u00famero de variaciones de orden\n-- k de un conjunto con n elementos. Por ejemplo,\n--    numeroVariaciones' 4 2  ==  12\n--    numeroVariaciones' 4 3  ==  24\n-- ---------------------------------------------------------------------\n\nnumeroVariaciones' :: Int -> Int -> Int\nnumeroVariaciones' n k = product [n-k+1..n]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 28. Definir la funci\u00f3n\n--    prop_numeroVariaciones :: Int -> Bool\n-- tal que (prop_numeroVariaciones n) se verifica si las funciones\n-- numeroVariaciones y numeroVariaciones' son equivalentes para\n-- los n primeros n\u00fameros y todo k entre 1 y n. Por ejemplo,\n--    prop_numeroVariaciones 5  ==  True\n-- ---------------------------------------------------------------------\n\nprop_numeroVariaciones :: Int -> Bool\nprop_numeroVariaciones n =\n  and [numeroVariaciones n k == numeroVariaciones' n k | k <- [1..n]]\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Variaciones con repetici\u00f3n\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 28. Definir la funci\u00f3n\n--    variacionesR :: Int -> [a] -> [[a]]\n-- tal que (variacionesR k xs) es la lista de las variaciones de orden\n-- k de los elementos de xs con repeticiones. Por ejemplo,\n--    ghci> variacionesR 1 \"ab\"\n--    [\"a\",\"b\"]\n--    ghci> variacionesR 2 \"ab\"\n--    [\"aa\",\"ab\",\"ba\",\"bb\"]\n--    ghci> variacionesR 3 \"ab\"\n--    [\"aaa\",\"aab\",\"aba\",\"abb\",\"baa\",\"bab\",\"bba\",\"bbb\"]\n-- ---------------------------------------------------------------------\n\nvariacionesR :: Int -> [a] -> [[a]]\nvariacionesR 0 _  = [[]] \nvariacionesR k xs =\n    [z:ys | z <- xs, ys <- variacionesR (k-1) xs]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 30. Definir la funci\u00f3n\n--    variacionesRN :: Int -> Int -> [[Int]]    \n-- tal que (variacionesRN n k) es la lista de las variaciones orden\n-- k de los primeros n n\u00fameros naturales. Por ejemplo,\n--    ghci> variacionesRN 3 2\n--    [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]\n--    ghci> variacionesRN 2 3\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]]\n-- ---------------------------------------------------------------------\n\nvariacionesRN :: Int -> Int -> [[Int]]    \nvariacionesRN n k = variacionesR k [1..n]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 31. Definir, usando variacionesR, la funci\u00f3n\n--    numeroVariacionesR :: Int -> Int -> Int\n-- tal que (numeroVariacionesR n k) es el n\u00famero de variaciones con\n-- repetici\u00f3n de orden k de un conjunto con n elementos. Por ejemplo,\n--    numeroVariacionesR 3 2  ==  9\n--    numeroVariacionesR 2 3  ==  8\n-- ---------------------------------------------------------------------\n\nnumeroVariacionesR :: Int -> Int -> Int\nnumeroVariacionesR n k = genericLength (variacionesRN n k)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 32. Definir, usando (^), la funci\u00f3n\n--    numeroVariacionesR' :: Int -> Int -> Int\n-- tal que (numeroVariacionesR' n k) es el n\u00famero de variaciones con\n-- repetici\u00f3n de orden k de un conjunto con n elementos. Por ejemplo,\n--    numeroVariacionesR' 3 2  ==  9\n--    numeroVariacionesR' 2 3  ==  8\n-- ---------------------------------------------------------------------\n\nnumeroVariacionesR' :: Int -> Int -> Int\nnumeroVariacionesR' n k = n^k\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 33. Definir la funci\u00f3n\n--    prop_numeroVariacionesR :: Int -> Bool\n-- tal que (prop_numeroVariacionesR n) se verifica si las funciones\n-- numeroVariacionesR y numeroVariacionesR' son equivalentes para\n-- los n primeros n\u00fameros y todo k entre 1 y n. Por ejemplo,\n--    prop_numeroVariacionesR 5  ==  True\n-- ---------------------------------------------------------------------\n\nprop_numeroVariacionesR :: Int -> Bool\nprop_numeroVariacionesR n =\n  and [numeroVariacionesR n k == numeroVariacionesR' n k | \n       k <- [1..n]]\n<\/pre>\n<p>Los ejercicios, y sus soluciones, de la primera parte se muestran a continuaci\u00f3n.<\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- El objetivo de esta relaci\u00f3n es redefinir algunos ejercicios de la\n-- relaci\u00f3n anterior usando la librer\u00eda de combinatoria que se instala\n-- con\n--    cabal install combinat\n\n-- ---------------------------------------------------------------------\n-- Importaci\u00f3n de librer\u00edas                                           --\n-- ---------------------------------------------------------------------\n\nimport Data.List (permutations)\nimport Math.Combinat.Sets\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Subconjuntos\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n \n--    subconjuntos :: [a] -> [[a]]\n-- tal que (subconjuntos xs) es la lista de las subconjuntos de la lista\n-- xs. Por ejemplo, \n--    ghci> subconjuntos [2,3,4]\n--    [[2,3,4],[2,3],[2,4],[2],[3,4],[3],[4],[]]\n--    ghci> subconjuntos [1,2,3,4]\n--    [[1,2,3,4],[1,2,3],[1,2,4],[1,2],[1,3,4],[1,3],[1,4],[1],\n--       [2,3,4],  [2,3],  [2,4],  [2],  [3,4],  [3],  [4], []]\n-- ---------------------------------------------------------------------\n\nsubconjuntos :: [a] -> [[a]]\nsubconjuntos = sublists\n \n-- ---------------------------------------------------------------------\n-- \u00a7 Permutaciones\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Definir la funci\u00f3n \n--    permutaciones :: [a] -> [[a]]  \n-- tal que (permutaciones xs) es la lista de las permutaciones de la\n-- lista xs. Por ejemplo,\n--    permutaciones \"bc\"   ==  [\"bc\",\"cb\"]\n--    permutaciones \"abc\"  ==  [\"abc\",\"bac\",\"bca\",\"acb\",\"cab\",\"cba\"]\n-- ---------------------------------------------------------------------\n \npermutaciones :: [a] -> [[a]]\npermutaciones = permutations\n\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Combinaciones          \n-- ---------------------------------------------------------------------  \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13. Definir la funci\u00f3n \n--    combinaciones :: Int -> [a] -> [[a]]\n-- tal que (combinaciones k xs) es la lista de las combinaciones de\n-- orden k de los elementos de la lista xs. Por ejemplo,\n--    ghci> combinaciones 2 \"bcde\"\n--    [\"bc\",\"bd\",\"be\",\"cd\",\"ce\",\"de\"]\n--    ghci> combinaciones 3 \"bcde\"\n--    [\"bcd\",\"bce\",\"bde\",\"cde\"]\n--    ghci> combinaciones 3 \"abcde\"\n--    [\"abc\",\"abd\",\"abe\",\"acd\",\"ace\",\"ade\",\"bcd\",\"bce\",\"bde\",\"cde\"]\n-- ---------------------------------------------------------------------\n \ncombinaciones :: Int -> [a] -> [[a]]\ncombinaciones = choose\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 15. Definir, usando combinacionesN, la funci\u00f3n\n--    numeroCombinaciones :: Int -> Int -> Integer\n-- tal que (numeroCombinaciones n k) es el n\u00famero de combinaciones de\n-- orden k de un conjunto con n elementos. Por ejemplo,\n--    numeroCombinaciones 4 2  ==  6\n--    numeroCombinaciones 4 3  ==  4\n-- ---------------------------------------------------------------------\n\nnumeroCombinaciones :: Int -> Int -> Integer\nnumeroCombinaciones n k = countKSublists k n\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Combinaciones con repetici\u00f3n\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 19. Definir la funci\u00f3n\n--    combinacionesR :: Int -> [a] -> [[a]]\n-- tal que (combinacionesR k xs) es la lista de las combinaciones orden\n-- k de los elementos de xs con repeticiones. Por ejemplo,\n--    ghci> combinacionesR 2 \"abc\"\n--    [\"aa\",\"ab\",\"ac\",\"bb\",\"bc\",\"cc\"]\n--    ghci> combinacionesR 3 \"bc\"\n--    [\"bbb\",\"bbc\",\"bcc\",\"ccc\"]\n--    ghci> combinacionesR 3 \"abc\"\n--    [\"aaa\",\"aab\",\"aac\",\"abb\",\"abc\",\"acc\",\"bbb\",\"bbc\",\"bcc\",\"ccc\"]\n-- ---------------------------------------------------------------------\n\ncombinacionesR :: Int -> [a] -> [[a]]\ncombinacionesR = combine\n\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Variaciones\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 24. Definir la funci\u00f3n \n--    variaciones :: Int -> [a] -> [[a]]\n-- tal que (variaciones n xs) es la lista de las variaciones n-arias\n-- de la lista xs. Por ejemplo,\n--    variaciones 2 \"abc\"  ==  [\"ab\",\"ba\",\"ac\",\"ca\",\"bc\",\"cb\"]\n-- ---------------------------------------------------------------------\n \nvariaciones :: Int -> [a] -> [[a]]\nvariaciones k xs = concatMap permutations (choose k xs)\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Variaciones con repetici\u00f3n\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 28. Definir la funci\u00f3n\n--    variacionesR :: Int -> [a] -> [[a]]\n-- tal que (variacionesR k xs) es la lista de las variaciones de orden\n-- k de los elementos de xs con repeticiones. Por ejemplo,\n--    ghci> variacionesR 1 \"ab\"\n--    [\"a\",\"b\"]\n--    ghci> variacionesR 2 \"ab\"\n--    [\"aa\",\"ab\",\"ba\",\"bb\"]\n--    ghci> variacionesR 3 \"ab\"\n--    [\"aaa\",\"aab\",\"aba\",\"abb\",\"baa\",\"bab\",\"bba\",\"bbb\"]\n-- ---------------------------------------------------------------------\n\nvariacionesR :: Int -> [a] -> [[a]]\nvariacionesR = tuplesFromList\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la primera 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 de la relaci\u00f3n 24 cuyo objetivo 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&#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":[265],"tags":[270,316],"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\/5944"}],"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=5944"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5944\/revisions"}],"predecessor-version":[{"id":5945,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5944\/revisions\/5945"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5944"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5944"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5944"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}