En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han explicado las soluciones de los ejercicios 13 a 34 de la 17\u00aa relaci\u00f3n<\/a>. <\/p>\n 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 Adem\u00e1s, se estudia dos temas relacionados: <\/p>\n Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n. En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se han explicado las soluciones de los ejercicios 13 a 34 de la 17\u00aa relaci\u00f3n. El objetivo de esta relaci\u00f3n es estudiar la generaci\u00f3n y el n\u00famero de las principales operaciones de la combinatoria. En concreto, se estudia Permutaciones. Combinaciones sin repetici\u00f3n…..<\/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":[1],"tags":[295],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1911"}],"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=1911"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1911\/revisions"}],"predecessor-version":[{"id":1986,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1911\/revisions\/1986"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1911"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1911"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1911"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\n
\n
\n<\/p>\n\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-- 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":"