-- I1M 2021-22: Relación 23
-- Combinatoria
-- Departamento de Ciencias de la Computación e Inteligencia Artificial
-- Universidad de Sevilla
-- ============================================================================
-- ============================================================================
-- Subconjuntos
-- ============================================================================
-- ----------------------------------------------------------------------------
-- Ejercicio 1. Definir la función
-- subconjuntos :: [a] -> [[a]]
-- tal que '(subconjuntos xs)' es la lista de las subconjuntos de la lista
-- 'xs'. Por ejemplo,
-- subconjuntos [2,3,4] ==
-- [[2,3,4],[2,3],[2,4],[2],[3,4],[3],[4],[]]
-- 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) = (map (x:) ys) ++ ys
where ys = subconjuntos xs
-- ============================================================================
-- Permutaciones
-- ============================================================================
-- ----------------------------------------------------------------------------
-- Ejercicio 2. Definir la función
-- intercala :: a -> [a] -> [[a]]
-- tal que '(intercala x ys)' es la lista de las listas obtenidas intercalando
-- el elemento 'x' entre los elementos de la lista '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)] ++ (map (y:) (intercala x ys))
-- ----------------------------------------------------------------------------
-- Ejercicio 3. Definir la función
-- permutaciones :: [a] -> [[a]]
-- tal que '(permutaciones xs)' es la lista de las permutaciones de la lista
-- 'xs'. Por ejemplo,
-- permutaciones "bc" == ["bc","cb"]
-- permutaciones "abc" == ["abc","bac","bca","acb","cab","cba"]
-- ----------------------------------------------------------------------------
permutaciones :: [a] -> [[a]]
permutaciones [] = [[]]
permutaciones (x:xs) = concat (map (intercala x) (permutaciones xs))
-- ----------------------------------------------------------------------------
-- Ejercicio 4. Definir la función
-- permutacionesN :: Integer -> [[Integer]]
-- tal que '(permutacionesN n)' es la lista de las permutaciones de los 'n'
-- primeros números naturales positivos. Por ejemplo,
-- permutacionesN 3 == [[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]
-- ----------------------------------------------------------------------------
permutacionesN :: Integer -> [[Integer]]
permutacionesN n = permutaciones [1..n]
-- ----------------------------------------------------------------------------
-- Ejercicio 5. Definir la función
-- numeroPermutacionesL :: Integer -> Integer
-- tal que '(numeroPermutacionesL n)' es el número de permutaciones de un
-- conjunto con 'n' elementos, calculado usando la función 'permutacionesN'.
-- Por ejemplo,
-- numeroPermutacionesL 3 == 6
-- numeroPermutacionesL 4 == 24
-- ----------------------------------------------------------------------------
numeroPermutacionesL :: Integer -> Integer
numeroPermutacionesL n = fromIntegral (length (permutacionesN n))
-- ----------------------------------------------------------------------------
-- Ejercicio 6. Definir la función
-- numeroPermutacionesF :: Integer -> Integer
-- tal que '(numeroPermutacionesF n)' es el número de permutaciones de un
-- conjunto con 'n' elementos, calculado usando la fórmula
-- P(n) = n!
-- Por ejemplo,
-- numeroPermutacionesF 3 == 6
-- numeroPermutacionesF 4 == 24
-- ----------------------------------------------------------------------------
numeroPermutacionesF :: Integer -> Integer
numeroPermutacionesF n = product [1..n]
-- ----------------------------------------------------------------------------
-- Ejercicio 7. Definir la función
-- prop_numeroPermutaciones :: Integer -> Bool
-- tal que '(prop_numeroPermutaciones n)' se verifica si las funciones
-- 'numeroPermutacionesL' y 'numeroPermutacionesF' son equivalentes para los
-- desde 1 hasta n. Por ejemplo,
-- prop_numeroPermutaciones 5 == True
-- ----------------------------------------------------------------------------
prop_numeroPermutaciones :: Integer -> Bool
prop_numeroPermutaciones n = and [numeroPermutacionesL x ==
numeroPermutacionesF x | x <- [1..n]]
-- ============================================================================
-- Permutaciones con repetición
-- ============================================================================
-- ----------------------------------------------------------------------------
-- Ejercicio 8. Definir la función
-- intercalaRep :: (Eq a) => a -> [a] -> [[a]]
-- tal que '(intercalaRep x ys)' es la lista de las listas obtenidas
-- intercalando el elemento 'x' entre los elementos de la lista 'ys', hasta la
-- primera ocurrencia del elemento 'x' en 'ys'. Por ejemplo,
-- intercalaRep 1 [1,2,1] == [[1,1,2,1]]
-- intercalaRep 1 [2,1,1] == [[1,2,1,1],[2,1,1,1]]
-- intercalaRep 1 [2,2,1] == [[1,2,2,1],[2,1,2,1],[2,2,1,1]]
-- ----------------------------------------------------------------------------
intercalaRep :: (Eq a) => a -> [a] -> [[a]]
intercalaRep x [] = [[x]]
intercalaRep x (y:ys) | x == y = [(x:y:ys)]
| otherwise = [(x:y:ys)] ++ (map (y:) (intercalaRep x ys))
-- ----------------------------------------------------------------------------
-- Ejercicio 9. Definir la función
-- permutacionesRep :: (Eq a) => [a] -> [[a]]
-- tal que '(permutacionesRep xs)' es la lista (sin elementos repetidos) de
-- las permutaciones con repetición de la lista 'xs'. Por ejemplo,
-- permutacionesRep "aba" == ["aba","baa","aab"]
-- permutacionesRep "abab" == ["abab","baab","aabb","abba","baba","bbaa"]
-- ----------------------------------------------------------------------------
permutacionesRep :: (Eq a) => [a] -> [[a]]
permutacionesRep [] = [[]]
permutacionesRep (x:xs) = concat (map (intercalaRep x) (permutacionesRep xs))
-- ----------------------------------------------------------------------------
-- Ejercicio 10. Definir la función
-- permutacionesRepN :: Integer -> Integer -> [[Integer]]
-- tal que '(permutacionesRepN n k)' es la lista de las permutaciones con
-- repetición de los 'n' primeros números naturales positivos con 'k'
-- repeticiones de cada uno de ellos. Por ejemplo,
-- permutacionesRepN 2 2 ==
-- [[1,2,1,2],[2,1,1,2],[1,1,2,2],[1,2,2,1],[2,1,2,1],[2,2,1,1]]
-- ----------------------------------------------------------------------------
permutacionesRepN :: Integer -> Integer -> [[Integer]]
permutacionesRepN n k = permutacionesRep (concat (replicate (fromInteger k) [1..n]))
-- ----------------------------------------------------------------------------
-- Ejercicio 11. Definir la función
-- numeroPermutacionesRepL :: Integer -> Integer -> Integer
-- tal que '(numeroPermutacionesRepL n k)' es el número de permutaciones con
-- repetición de un conjunto con 'k*n' elementos, donde cada uno de ellos se
-- repite 'k' veces, calculado usando la función 'permutacionesRepN'. Por
-- ejemplo,
-- numeroPermutacionesRepL 2 2 == 6
-- numeroPermutacionesRepL 2 3 == 20
-- numeroPermutacionesRepL 3 2 == 90
-- ----------------------------------------------------------------------------
numeroPermutacionesRepL :: Integer -> Integer -> Integer
numeroPermutacionesRepL n k = toInteger (length (permutacionesRepN n k))
-- ----------------------------------------------------------------------------
-- Ejercicio 12. Definir la función
-- numeroPermutacionesRepF :: Integer -> Integer -> Integer
-- tal que '(numeroPermutacionesRepF n k)' es el número de permutaciones con
-- repetición de un conjunto con 'k*n' elementos, donde cada uno de ellos se
-- repite 'k' veces, calculado usando la fórmula
-- n!
-- PR(n,[a,b,c,...]) = --------------------
-- a! * b! * c! * ...
-- Por ejemplo,
-- numeroPermutacionesRepF 2 2 == 6
-- numeroPermutacionesRepF 2 3 == 20
-- numeroPermutacionesRepF 3 2 == 90
-- ----------------------------------------------------------------------------
numeroPermutacionesRepF :: Integer -> Integer -> Integer
numeroPermutacionesRepF n k = (product [1..n*k]) `div` (product (replicate (fromInteger n) (product [1..k])))
-- ----------------------------------------------------------------------------
-- Ejercicio 13. Definir la función
-- prop_numeroPermutacionesRep :: Integer -> Bool
-- tal que '(prop_numeroPermutacionesRep n)' se verifica si las funciones
-- 'numeroPermutacionesRepL' y 'numeroPermutacionesRepF' son equivalentes para
-- los 'n' primeros números naturales positivos y para todo 'k' entre 1 y 'n'.
-- Por ejemplo,
-- prop_numeroPermutacionesRep 3 == True
-- ----------------------------------------------------------------------------
prop_numeroPermutacionesRep :: Integer -> Bool
prop_numeroPermutacionesRep n = and [numeroPermutacionesRepL x k ==
numeroPermutacionesRepF x k
| x <- [1..n], k <- [1..x]]
-- ============================================================================
-- Combinaciones
-- ============================================================================
-- ----------------------------------------------------------------------------
-- Ejercicio 14. Definir la función
-- combinaciones :: Integer -> [a] -> [[a]]
-- tal que '(combinaciones k xs)' es la lista de las combinaciones de orden 'k'
-- de los elementos de la lista 'xs'. Por ejemplo,
-- combinaciones 2 "bcde" == ["bc","bd","be","cd","ce","de"]
-- combinaciones 3 "bcde" == ["bcd","bce","bde","cde"]
-- combinaciones 3 "abcde" ==
-- ["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]
-- ----------------------------------------------------------------------------
combinaciones :: Integer -> [a] -> [[a]]
combinaciones k xs = filter ((==fromInteger(k)) . length) (subconjuntos xs)
-- ----------------------------------------------------------------------------
-- Ejercicio 15. Definir la función
-- combinacionesN :: Integer -> Integer -> [[Integer]]
-- tal que '(combinacionesN k n)' es la lista de las combinaciones de orden 'k'
-- de los 'n' primeros números naturales positivos. Por ejemplo,
-- combinacionesN 2 4 == [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
-- combinacionesN 3 4 == [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
-- ----------------------------------------------------------------------------
combinacionesN :: Integer -> Integer -> [[Integer]]
combinacionesN k n = combinaciones k [1..n]
-- ----------------------------------------------------------------------------
-- Ejercicio 16. Definir la función
-- numeroCombinacionesL :: Integer -> Integer -> Integer
-- tal que '(numeroCombinacionesL k n)' es el número de combinaciones de orden
-- 'k' de un conjunto con 'n' elementos, calculado usando la función
-- 'combinacionesN'. Por ejemplo,
-- numeroCombinacionesL 2 4 == 6
-- numeroCombinacionesL 3 4 == 4
-- ----------------------------------------------------------------------------
numeroCombinacionesL :: Integer -> Integer -> Integer
numeroCombinacionesL k n = toInteger (length (combinacionesN k n))
-- ----------------------------------------------------------------------------
-- Ejercicio 17. Definir la función 'comb' tal que '(comb n k)' es el número
-- combinatorio 'n' sobre 'k'; es decir, (comb n k) = n! / (k!(n-k)!). Por
-- ejemplo,
-- comb 4 2 == 6
-- comb 4 3 == 4
-- ----------------------------------------------------------------------------
comb :: Integer -> Integer -> Integer
comb n k = (product [1..n]) `div` ((product [1..k])*(product [1..n-k]))
-- ----------------------------------------------------------------------------
-- Ejercicio 18. Definir la función
-- numeroCombinacionesF :: Integer -> Integer -> Integer
-- tal que '(numeroCombinacionesF k n)' es el número de combinaciones de orden
-- 'k' de un conjunto con 'n' elementos, calculado usando la fórmula
-- / n \ n!
-- C(n,k) = | | = -------------
-- \ k / k! * (n-k)!
-- Por ejemplo,
-- numeroCombinacionesF 2 4 == 6
-- numeroCombinacionesF 3 4 == 4
-- ----------------------------------------------------------------------------
numeroCombinacionesF :: Integer -> Integer -> Integer
numeroCombinacionesF k n = comb n k
-- ----------------------------------------------------------------------------
-- Ejercicio 19. Definir la función
-- prop_numeroCombinaciones :: Integer -> Bool
-- tal que '(prop_numeroCombinaciones n)' se verifica si las funciones
-- 'numeroCombinaciones' y 'numeroCombinacionesC' son equivalentes para los 'n'
-- primeros números naturales positivos y para todo 'k' entre 1 y 'n'. Por
-- ejemplo,
-- prop_numeroCombinaciones 5 == True
-- ----------------------------------------------------------------------------
prop_numeroCombinaciones :: Integer -> Bool
prop_numeroCombinaciones n = and [numeroCombinacionesL k x ==
numeroCombinacionesF k x | x <- [1..n], k <- [1..x]]
-- ============================================================================
-- Combinaciones con repetición
-- ============================================================================
-- ----------------------------------------------------------------------------
-- Ejercicio 20. Definir la función
-- combinacionesRep :: Integer -> [a] -> [[a]]
-- tal que '(combinacionesRep k xs)' es la lista de las combinaciones con
-- repetición de orden 'k' de los elementos de la lista 'xs'. Por ejemplo,
-- combinacionesRep 2 "abc" == ["aa","ab","ac","bb","bc","cc"]
-- combinacionesRep 3 "bc" == ["bbb","bbc","bcc","ccc"]
-- combinacionesRep 3 "abc" ==
-- ["aaa","aab","aac","abb","abc","acc","bbb","bbc","bcc","ccc"]
-- ----------------------------------------------------------------------------
combinacionesRep :: Integer -> [a] -> [[a]]
combinacionesRep 0 _ = [[]]
combinacionesRep n [] = []
combinacionesRep n (x:xs) = (map (x:) (combinacionesRep (n-1) (x:xs))) ++ combinacionesRep n xs
-- ----------------------------------------------------------------------------
-- Ejercicio 21. Definir la función
-- combinacionesRepN :: Integer -> Integer -> [[Integer]]
-- tal que '(combinacionesRepN k n)' es la lista de las combinaciones con
-- repetición de orden 'k' de los 'n' primeros números naturales positivos. Por
-- ejemplo,
-- combinacionesRepN 2 3 == [[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]]
-- combinacionesRepN 3 2 == [[1,1,1],[1,1,2],[1,2,2],[2,2,2]]
-- ----------------------------------------------------------------------------
combinacionesRepN :: Integer -> Integer -> [[Integer]]
combinacionesRepN k n = combinacionesRep k [1..n]
-- ----------------------------------------------------------------------------
-- Ejercicio 22. Definir la función
-- numeroCombinacionesRepL :: Integer -> Integer -> Integer
-- tal que '(numeroCombinacionesRepL k n)' es el número de combinaciones con
-- repetición de orden 'k' de un conjunto con 'n' elementos, calculado usando
-- la función 'combinacionesRepN'. Por ejemplo,
-- numeroCombinacionesRepL 2 3 == 6
-- numeroCombinacionesRepL 3 2 == 4
-- ----------------------------------------------------------------------------
numeroCombinacionesRepL :: Integer -> Integer -> Integer
numeroCombinacionesRepL k n = toInteger (length (combinacionesRepN k n))
-- ----------------------------------------------------------------------------
-- Ejercicio 23. Definir la función
-- numeroCombinacionesRepF :: Integer -> Integer -> Integer
-- tal que '(numeroCombinacionesRepF k n)' es el número de combinaciones con
-- repetición de orden 'k' de un conjunto con 'n' elementos, calculado usando
-- la fórmula
-- / n+k-1 \ (n+k-1)!
-- CR(n,k) = | | = -------------
-- \ k / k! * (n-1)!
-- Por ejemplo,
-- numeroCombinacionesRepF 2 3 == 6
-- numeroCombinacionesRepF 3 2 == 4
-- ----------------------------------------------------------------------------
numeroCombinacionesRepF :: Integer -> Integer -> Integer
numeroCombinacionesRepF k n = comb (n+k-1) k
-- ----------------------------------------------------------------------------
-- Ejercicio 24. Definir la función
-- prop_numeroCombinacionesRep :: Integer -> Bool
-- tal que '(prop_numeroCombinacioneRep n)' se verifica si las funciones
-- 'numeroCombinacionesRepL' y 'numeroCombinacionesRepF' son equivalentes para
-- los 'n' primeros números naturales positivos y para todo 'k' entre 1 y 'n'.
-- Por ejemplo,
-- prop_numeroCombinacionesRep 5 == True
-- ----------------------------------------------------------------------------
prop_numeroCombinacionesRep :: Integer -> Bool
prop_numeroCombinacionesRep n = and [numeroCombinacionesRepL k x ==
numeroCombinacionesRepF k x
| x <- [1..n], k <- [1..x]]
-- ============================================================================
-- Variaciones
-- ============================================================================
-- ----------------------------------------------------------------------------
-- Ejercicio 25. Definir la función
-- variaciones :: Integer -> [a] -> [[a]]
-- tal que '(variaciones k xs)' es la lista de las variaciones de orden 'k' de
-- los elementos de la lista 'xs'. Por ejemplo,
-- variaciones 2 "abc" == ["ab","ba","ac","ca","bc","cb"]
-- ----------------------------------------------------------------------------
variaciones :: Integer -> [a] -> [[a]]
variaciones 0 xs = [[]]
variaciones n [] = []
variaciones n (x:xs) = concat (map (intercala x) (variaciones (n-1) xs))
++ variaciones n xs
-- ----------------------------------------------------------------------------
-- Ejercicio 26. Definir la función
-- variacionesN :: Integer -> Integer -> [[Integer]]
-- tal que '(variacionesN k n)' es la lista de las variaciones de orden 'k' de
-- los 'n' primeros números naturales positivos. Por ejemplo,
-- variacionesN 2 3 == [[1,2],[2,1],[1,3],[3,1],[2,3],[3,2]]
-- ----------------------------------------------------------------------------
variacionesN :: Integer -> Integer -> [[Integer]]
variacionesN k n = variaciones k [1..n]
-- ----------------------------------------------------------------------------
-- Ejercicio 27. Definir la función
-- numeroVariacionesL :: Integer -> Integer -> Integer
-- tal que '(numeroVariacionesL k n)' es el número de variaciones de orden 'k'
-- de un conjunto con 'n' elementos, calculado usando la función
-- 'variacionesN'. Por ejemplo,
-- numeroVariacionesL 2 4 == 12
-- numeroVariacionesL 3 4 == 24
-- ----------------------------------------------------------------------------
numeroVariacionesL :: Integer -> Integer -> Integer
numeroVariacionesL k n = toInteger (length (variacionesN k n))
-- ----------------------------------------------------------------------------
-- Ejercicio 28. Definir la función
-- numeroVariacionesF :: Integer -> Integer -> Integer
-- tal que '(numeroVariacionesF k n)' es el número de variaciones de orden 'k'
-- de un conjunto con 'n' elementos, calculado usando la fórmula
-- n!
-- V(n,k) = --------
-- (n-k)!
-- Por ejemplo,
-- numeroVariacionesF 2 4 == 12
-- numeroVariacionesF 3 4 == 24
-- ----------------------------------------------------------------------------
numeroVariacionesF :: Integer -> Integer -> Integer
numeroVariacionesF k n = (product [1..n]) `div` (product [1..(n-k)])
-- ----------------------------------------------------------------------------
-- Ejercicio 29. Definir la función
-- prop_numeroVariaciones :: Integer -> Bool
-- tal que '(prop_numeroVariaciones n)' se verifica si las funciones
-- 'numeroVariacionesL' y 'numeroVariacionesF' son equivalentes para los 'n'
-- primeros números naturales positivos y para todo 'k' entre 1 y 'n'. Por
-- ejemplo,
-- prop_numeroVariaciones 5 == True
-- ----------------------------------------------------------------------------
prop_numeroVariaciones :: Integer -> Bool
prop_numeroVariaciones n = and [numeroVariacionesL k x ==
numeroVariacionesF k x
| x <- [1..n], k <- [1..x]]
-- ============================================================================
-- Variaciones con repetición
-- ============================================================================
-- ----------------------------------------------------------------------------
-- Ejercicio 30. Definir la función
-- variacionesRep :: Integer -> [a] -> [[a]]
-- tal que '(variacionesRep k xs)' es la lista de las variaciones con
-- repetición de orden 'k' de los elementos de la lista 'xs'. Por ejemplo,
-- variacionesRep 1 "ab" == ["a","b"]
-- variacionesRep 2 "ab" == ["aa","ab","ba","bb"]
-- variacionesRep 3 "ab" ==
-- ["aaa","aab","aba","abb","baa","bab","bba","bbb"]
-- ----------------------------------------------------------------------------
variacionesRep :: Integer -> [a] -> [[a]]
variacionesRep 0 xs = [[]]
variacionesRep n xs = [x:ys | x <- xs, ys <- variacionesRep (n-1) xs]
-- ----------------------------------------------------------------------------
-- Ejercicio 31. Definir la función
-- variacionesRepN :: Integer -> Integer -> [[Integer]]
-- tal que '(variacionesRepN k n)' es la lista de las variaciones con
-- repetición de orden 'k' de los 'n' primeros números naturales positivos. Por
-- ejemplo,
-- variacionesRepN 2 3 ==
-- [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]
-- variacionesRepN 3 2 ==
-- [[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,1],[2,1,2],[2,2,1],[2,2,2]]
-- ----------------------------------------------------------------------------
variacionesRepN :: Integer -> Integer -> [[Integer]]
variacionesRepN k n = variacionesRep k [1..n]
-- ----------------------------------------------------------------------------
-- Ejercicio 32. Definir la función
-- numeroVariacionesRepL :: Integer -> Integer -> Integer
-- tal que '(numeroVariacionesRepL k n)' es el número de variaciones con
-- repetición de orden 'k' de un conjunto con 'n' elementos, calculado usando
-- la función 'variacionesRepN'. Por ejemplo,
-- numeroVariacionesRepL 2 3 == 9
-- numeroVariacionesRepL 3 2 == 8
-- ----------------------------------------------------------------------------
numeroVariacionesRepL :: Integer -> Integer -> Integer
numeroVariacionesRepL k n = toInteger (length (variacionesRepN k n))
-- ----------------------------------------------------------------------------
-- Ejercicio 33. Definir la función
-- numeroVariacionesRepF :: Integer -> Integer -> Integer
-- tal que '(numeroVariacionesRepF k n)' es el número de variaciones con
-- repetición de orden 'k' de un conjunto con 'n' elementos, calculado usando
-- la fórmula
-- VR(n,k) = n^k
-- Por ejemplo,
-- numeroVariacionesRepF 2 3 == 9
-- numeroVariacionesRepF 3 2 == 8
-- ----------------------------------------------------------------------------
numeroVariacionesRepF :: Integer -> Integer -> Integer
numeroVariacionesRepF k n = n^k
-- ----------------------------------------------------------------------------
-- Ejercicio 34. Definir la función
-- prop_numeroVariacionesRep :: Integer -> Bool
-- tal que '(prop_numeroVariacionesRep n)' se verifica si las funciones
-- 'numeroVariacionesRepL' y 'numeroVariacionesRepF' son equivalentes para los
-- 'n' primeros números naturales positivos y para todo 'k' entre 1 y 'n'. Por
-- ejemplo,
-- prop_numeroVariacionesRep 5 == True
-- ----------------------------------------------------------------------------
prop_numeroVariacionesRep :: Integer -> Bool
prop_numeroVariacionesRep n = and [numeroVariacionesRepL k x ==
numeroVariacionesRepF k x
| x <- [1..n], k <- [1..x]]
-- ============================================================================