{"id":5363,"date":"2016-03-11T17:35:32","date_gmt":"2016-03-11T16:35:32","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5363"},"modified":"2016-03-13T07:39:06","modified_gmt":"2016-03-13T06:39:06","slug":"i1m2015-combinatoria-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2015-combinatoria-en-haskell\/","title":{"rendered":"I1M2015: Combinatoria en Haskell"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-15\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han explicado las soluciones de los ejercicios de la relaci\u00f3n 26 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>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\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-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir, mediante all, la funci\u00f3n \n--    subconjunto1 :: Eq a => [a] -> [a] -> Bool\n-- tal que (subconjunto1 xs ys) se verifica si xs es un subconjunto de\n-- ys. Por ejemplo,\n--    subconjunto1 [1,3,2,3] [1,2,3]  ==  True\n--    subconjunto1 [1,3,4,3] [1,2,3]  ==  False\n-- ---------------------------------------------------------------------\n \nsubconjunto1 :: Eq a => [a] -> [a] -> Bool\nsubconjunto1 xs ys = all (`elem` ys) xs\n \n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Comprobar con QuickCheck que las funciones subconjunto\n-- y subconjunto1 son equivalentes.\n-- ---------------------------------------------------------------------\n \n-- La propiedad es\nprop_equivalencia :: [Int] -> [Int] -> Bool\nprop_equivalencia xs ys =\n    subconjunto xs ys == subconjunto1 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\nsubconjuntos1 :: [a] -> [[a]]\nsubconjuntos1 []     = [[]]\nsubconjuntos1 (x:xs) = sub ++ map (x:) sub\n    where sub = subconjuntos1 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 :: Integer -> [[Integer]]\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\npermutacionesN :: Integer -> [[Integer]]\npermutacionesN n = permutaciones [1..n]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Definir, usando permutacionesN, la funci\u00f3n\n--    numeroPermutacionesN :: Integer -> Integer\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 :: Integer -> Integer\nnumeroPermutacionesN = genericLength . permutacionesN \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10. Definir la funci\u00f3n\n--    fact :: Integer -> Integer\n-- tal que (fact n) es el factorial de n. Por ejemplo,\n--    fact 3  ==  6\n-- ---------------------------------------------------------------------\n\nfact :: Integer -> Integer\nfact n = product [1..n]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11. Definir, usando fact, la funci\u00f3n\n--    numeroPermutacionesN1 :: Integer -> Integer\n-- tal que (numeroPermutacionesN1 n) es el n\u00famero de permutaciones de un\n-- conjunto con n elementos. Por ejemplo,\n--    numeroPermutacionesN1 3  ==  6\n--    numeroPermutacionesN1 4  ==  24\n-- ---------------------------------------------------------------------\n\nnumeroPermutacionesN1 :: Integer -> Integer\nnumeroPermutacionesN1 = fact\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 12. Definir la funci\u00f3n\n--    prop_numeroPermutacionesN :: Integer -> Bool\n-- tal que (prop_numeroPermutacionesN n) se verifica si las funciones\n-- numeroPermutacionesN y numeroPermutacionesN1 son equivalentes para\n-- los n primeros n\u00fameros. Por ejemplo,\n--    prop_numeroPermutacionesN 5  ==  True\n-- ---------------------------------------------------------------------\n\nprop_numeroPermutacionesN :: Integer -> Bool\nprop_numeroPermutacionesN n = \n    and [numeroPermutacionesN x == numeroPermutacionesN1 x | x <- [1..n]] \n\n-- ---------------------------------------------------------------------\n-- \u00a7 Combinaciones          \n-- ---------------------------------------------------------------------  \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13. Definir la funci\u00f3n \n--    combinaciones :: Integer -> [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 :: Integer -> [a] -> [[a]]\ncombinaciones1 n xs = \n    [ys | ys <- subconjuntos xs, genericLength ys == n]  \n \n-- 2\u00aa definici\u00f3n\ncombinaciones2 :: Integer -> [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 :: Integer -> [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 :: Integer -> [a] -> [[a]]\ncombinaciones = combinaciones2\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 14. Definir la funci\u00f3n\n--    combinacionesN :: Integer -> Integer -> [[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\ncombinacionesN :: Integer -> Integer -> [[Integer]]\ncombinacionesN n k = combinaciones k [1..n]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 15. Definir, usando combinacionesN, la funci\u00f3n\n--    numeroCombinaciones :: Integer -> Integer -> 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 :: Integer -> Integer -> Integer\nnumeroCombinaciones n k = genericLength (combinacionesN n k)\n\n-- Puede definirse por composici\u00f3n\nnumeroCombinaciones2 :: Integer -> Integer -> Integer\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 :: Integer -> Integer -> Integer\nnumeroCombinaciones3 = genericLength .: combinacionesN\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 16. Definir la funci\u00f3n\n--    comb :: Integer -> Integer -> Integer\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 :: Integer -> Integer -> Integer\ncomb n k = fact n `div` (fact k * fact (n-k))\n \n-- ---------------------------------------------------------------------\n-- Ejercicio 17. Definir, usando comb, la funci\u00f3n\n--    numeroCombinaciones1 :: Integer -> Integer -> Integer\n-- tal que (numeroCombinaciones1 n k) es el n\u00famero de combinaciones de\n-- orden k de un conjunto con n elementos. Por ejemplo,\n--    numeroCombinaciones1 4 2  ==  6\n--    numeroCombinaciones1 4 3  ==  4\n-- ---------------------------------------------------------------------\n\nnumeroCombinaciones1 :: Integer -> Integer -> Integer\nnumeroCombinaciones1 = comb \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 18. Definir la funci\u00f3n\n--    prop_numeroCombinaciones :: Integer -> Bool\n-- tal que (prop_numeroCombinaciones n) se verifica si las funciones\n-- numeroCombinaciones y numeroCombinaciones1 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 :: Integer -> Bool\nprop_numeroCombinaciones n =\n  and [numeroCombinaciones n k == numeroCombinaciones1 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 :: Integer -> [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 :: Integer -> [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 :: Integer -> Integer -> [[Integer]]    \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\ncombinacionesRN :: Integer -> Integer -> [[Integer]]    \ncombinacionesRN n k = combinacionesR k [1..n]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 21. Definir, usando combinacionesRN, la funci\u00f3n\n--    numeroCombinacionesR :: Integer -> Integer -> Integer\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 :: Integer -> Integer -> Integer\nnumeroCombinacionesR n k = genericLength (combinacionesRN n k)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 22. Definir, usando comb, la funci\u00f3n\n--    numeroCombinacionesR1 :: Integer -> Integer -> Integer\n-- tal que (numeroCombinacionesR1 n k) es el n\u00famero de combinaciones con\n-- repetici\u00f3n de orden k de un conjunto con n elementos. Por ejemplo,\n--    numeroCombinacionesR1 3 2  ==  6\n--    numeroCombinacionesR1 2 3  ==  4\n-- ---------------------------------------------------------------------\n\nnumeroCombinacionesR1 :: Integer -> Integer -> Integer\nnumeroCombinacionesR1 n k = comb (n+k-1) k\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 23. Definir la funci\u00f3n\n--    prop_numeroCombinacionesR :: Integer -> Bool\n-- tal que (prop_numeroCombinacionesR n) se verifica si las funciones\n-- numeroCombinacionesR y numeroCombinacionesR1 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 :: Integer -> Bool\nprop_numeroCombinacionesR n =\n  and [numeroCombinacionesR n k == numeroCombinacionesR1 n k | \n       k <- [1..n]]\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Variaciones\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 24. Definir la funci\u00f3n \n--    variaciones :: Integer -> [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 :: Integer -> [a] -> [[a]]\nvariaciones k xs = concatMap permutaciones (combinaciones k xs)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 25. Definir la funci\u00f3n\n--    variacionesN :: Integer -> Integer -> [[Integer]]\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 :: Integer -> Integer -> [[Integer]]\nvariacionesN n k = variaciones k [1..n]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 26. Definir, usando variacionesN, la funci\u00f3n\n--    numeroVariaciones :: Integer -> Integer -> Integer\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 :: Integer -> Integer -> Integer\nnumeroVariaciones n k = genericLength (variacionesN n k)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 27. Definir, usando product, la funci\u00f3n\n--    numeroVariaciones1 :: Integer -> Integer -> Integer\n-- tal que (numeroVariaciones1 n k) es el n\u00famero de variaciones de orden\n-- k de un conjunto con n elementos. Por ejemplo,\n--    numeroVariaciones1 4 2  ==  12\n--    numeroVariaciones1 4 3  ==  24\n-- ---------------------------------------------------------------------\n\nnumeroVariaciones1 :: Integer -> Integer -> Integer\nnumeroVariaciones1 n k = product [n-k+1..n]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 28. Definir la funci\u00f3n\n--    prop_numeroVariaciones :: Integer -> Bool\n-- tal que (prop_numeroVariaciones n) se verifica si las funciones\n-- numeroVariaciones y numeroVariaciones1 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 :: Integer -> Bool\nprop_numeroVariaciones n =\n  and [numeroVariaciones n k == numeroVariaciones1 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 :: Integer -> [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 :: Integer -> [a] -> [[a]]\nvariacionesR _ [] = [[]]\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 :: Integer -> Integer -> [[Integer]]    \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 :: Integer -> Integer -> [[Integer]]    \nvariacionesRN n k = variacionesR k [1..n]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 31. Definir, usando variacionesR, la funci\u00f3n\n--    numeroVariacionesR :: Integer -> Integer -> Integer\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 :: Integer -> Integer -> Integer\nnumeroVariacionesR n k = genericLength (variacionesRN n k)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 32. Definir, usando (^), la funci\u00f3n\n--    numeroVariacionesR1 :: Integer -> Integer -> Integer\n-- tal que (numeroVariacionesR1 n k) es el n\u00famero de variaciones con\n-- repetici\u00f3n de orden k de un conjunto con n elementos. Por ejemplo,\n--    numeroVariacionesR1 3 2  ==  9\n--    numeroVariacionesR1 2 3  ==  8\n-- ---------------------------------------------------------------------\n\nnumeroVariacionesR1 :: Integer -> Integer -> Integer\nnumeroVariacionesR1 n k = n^k\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 33. Definir la funci\u00f3n\n--    prop_numeroVariacionesR :: Integer -> Bool\n-- tal que (prop_numeroVariacionesR n) se verifica si las funciones\n-- numeroVariacionesR y numeroVariacionesR1 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 :: Integer -> Bool\nprop_numeroVariacionesR n =\n  and [numeroVariacionesR n k == numeroVariacionesR1 n k | \n       k <- [1..n]]\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 26 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 repetici\u00f3n Variaciones sin repetici\u00f3n&#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":[250],"tags":[270,310],"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\/5363"}],"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=5363"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5363\/revisions"}],"predecessor-version":[{"id":5365,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5363\/revisions\/5365"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5363"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5363"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5363"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}