I1M2011: Combinatoria en Haskell (1)
En segunda parte de la clase de hoy de Informática de 1º del Grado en Matemáticas se han explicado las soluciones de los 6 primeros ejercicios de la 16ª relación.
El objetivo de esta relación es estudiar la generación y el número de
las principales operaciones de la combinatoria. En concreto, se
estudia
- Permutaciones.
- Combinaciones sin repetición..
- Combinaciones con repetición
- Variaciones sin repetición.
- Variaciones con repetición.
Además, se estudia dos temas relacionados:
- Reconocimiento y generación de subconjuntos y
- El triángulo de Pascal
Los ejercicios, y sus soluciones, se muestran a continuación.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
-- --------------------------------------------------------------------- -- Importación de librerías -- -- --------------------------------------------------------------------- import Test.QuickCheck import Data.List (genericLength) -- --------------------------------------------------------------------- -- § Subconjuntos -- --------------------------------------------------------------------- -- --------------------------------------------------------------------- -- Ejercicio 1. Definir, por recursión, la función -- subconjunto :: Eq a => [a] -> [a] -> Bool -- tal que (subconjunto xs ys) se verifica si xs es un subconjunto de -- ys. Por ejemplo, -- subconjunto [1,3,2,3] [1,2,3] == True -- subconjunto [1,3,4,3] [1,2,3] == False -- --------------------------------------------------------------------- subconjunto :: Eq a => [a] -> [a] -> Bool subconjunto [] _ = True subconjunto (x:xs) ys = elem x ys && subconjunto xs ys -- --------------------------------------------------------------------- -- Ejercicio 2. Definir, mediante all, la función -- subconjunto' :: Eq a => [a] -> [a] -> Bool -- tal que (subconjunto' xs ys) se verifica si xs es un subconjunto de -- ys. Por ejemplo, -- subconjunto' [1,3,2,3] [1,2,3] == True -- subconjunto' [1,3,4,3] [1,2,3] == False -- --------------------------------------------------------------------- subconjunto' :: Eq a => [a] -> [a] -> Bool subconjunto' xs ys = all (`elem` ys) xs -- --------------------------------------------------------------------- -- Ejercicio 3. Comprobar con QuickCheck que las funciones subconjunto -- y subconjunto' son equivalentes. -- --------------------------------------------------------------------- -- La propiedad es prop_equivalencia :: [Int] -> [Int] -> Bool prop_equivalencia xs ys = subconjunto xs ys == subconjunto' xs ys -- La comprobación es -- ghci> quickCheck prop_equivalencia -- OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 4. Definir la función -- igualConjunto :: Eq a => [a] -> [a] -> Bool -- tal que (igualConjunto xs ys) se verifica si las listas xs e ys, -- vistas como conjuntos, son iguales. Por ejemplo, -- igualConjunto [1..10] [10,9..1] == True -- igualConjunto [1..10] [11,10..1] == False -- --------------------------------------------------------------------- igualConjunto :: Eq a => [a] -> [a] -> Bool igualConjunto xs ys = subconjunto xs ys && subconjunto ys xs -- --------------------------------------------------------------------- -- Ejercicio 5. Definir la función -- subconjuntos :: [a] -> [[a]] -- tal que (subconjuntos xs) es la lista de las subconjuntos de la lista -- xs. Por ejemplo, -- ghci> subconjuntos [2,3,4] -- [[2,3,4],[2,3],[2,4],[2],[3,4],[3],[4],[]] -- ghci> subconjuntos [1,2,3,4] -- [[1,2,3,4],[1,2,3],[1,2,4],[1,2],[1,3,4],[1,3],[1,4],[1], -- [2,3,4], [2,3], [2,4], [2], [3,4], [3], [4], []] -- --------------------------------------------------------------------- subconjuntos :: [a] -> [[a]] subconjuntos [] = [[]] subconjuntos (x:xs) = [x:ys | ys <- sub] ++ sub where sub = subconjuntos xs -- Cambiando la comprensión por map se obtiene subconjuntos' :: [a] -> [[a]] subconjuntos' [] = [[]] subconjuntos' (x:xs) = sub ++ map (x:) sub where sub = subconjuntos' xs -- --------------------------------------------------------------------- -- § Permutaciones -- --------------------------------------------------------------------- -- --------------------------------------------------------------------- -- Ejercicio 6. Definir la función -- intercala :: a -> [a] -> [[a]] -- tal que (intercala x ys) es la lista de las listas obtenidas -- intercalando x entre los elementos de ys. Por ejemplo, -- intercala 1 [2,3] == [[1,2,3],[2,1,3],[2,3,1]] -- --------------------------------------------------------------------- intercala :: a -> [a] -> [[a]] intercala x [] = [[x]] intercala x (y:ys) = (x:y:ys) : [y:zs | zs <- intercala x ys] |