Relación 23

-- 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], []]
-- ----------------------------------------------------------------------------
--Daniel Cebrián Castillo
subconjuntos :: [a] -> [[a]]
subconjuntos xs | null xs = [[]]
                | otherwise = map ([xs!!0]++) (subconjuntos(tail xs)) ++ subconjuntos (tail xs)


-- Álvaro Galisteo: 

subconjuntos :: [a] -> [[a]]
subconjuntos [] = [[]]
subconjuntos (x:xs) = [x:ys | ys <- sub] ++ sub
                   where sub = 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]]
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
intercala :: a -> [a] -> [[a]]
intercala i xs = [ take n xs ++ [i] ++ drop n xs | n<-[0..length xs]]


-- Álvaro Galisteo: 

intercala :: a -> [a] -> [[a]]
intercala x ys = [take n ys ++ [x] ++ take (length ys - n) (drop n ys)| n <- [0..(length 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"]
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
permutaciones :: [a] -> [[a]]
permutaciones [] = [[]]
permutaciones (x:xs) = concat[(intercala x p) |p<-permutaciones xs ] 


-- Álvaro Galisteo: 

permutaciones :: [a] -> [[a]]
permutaciones [x] = [[x]]
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]]
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
permutacionesN :: Integer -> [[Integer]]
permutacionesN n = permutaciones [ j | j<-[1..n]]


-- Álvaro Galisteo: 

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
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
numeroPermutacionesL :: Integer -> Integer
numeroPermutacionesL n = fromIntegral (length (permutacionesN n))


-- Álvaro Galisteo:

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
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
numeroPermutacionesF :: Integer -> Integer
numeroPermutacionesF 0 = 1
numeroPermutacionesF n =  n*numeroPermutacionesF (n-1)


-- Álvaro Galisteo: 

numeroPermutacionesF :: Integer -> Integer
numeroPermutacionesF n = product [2..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
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
prop_numeroPermutaciones :: Integer -> Bool
prop_numeroPermutaciones n = and [numeroPermutacionesF k == numeroPermutacionesL k | k<-[1..n]]


-- Álvaro Galisteo: 

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]]
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
--fstaparcion es una función que devuelve la primera aparición de un elemento en un conjunto
fstaparicion :: (Eq a)=> a -> [a] -> Int
fstaparicion i xs = length xs - length (dropWhile (i/=) xs)

intercalaRep :: (Eq a) => a -> [a] -> [[a]]
intercalaRep i xs = [ take n xs ++ [i] ++ drop n xs | n<-[0..ii]]
  where ii = fstaparicion I xs


-- Álvaro Galisteo:

intercalaRep :: (Eq a) => a -> [a] -> [[a]]
intercalaRep x ys = [take n ys ++ [x] ++ take (length ys - n) (drop n ys)| n <- [0..z]]
                  where z = length (takeWhile (/= 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"]
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
permutacionesRep :: (Eq a) => [a] -> [[a]]
permutacionesRep [] =[[]]
permutacionesRep (x:xs) = concat [ intercalaRep x p |p<- permutacionesRep xs]


-- Álvaro Galisteo: 

permutacionesRep :: (Eq a) => [a] -> [[a]]
permutacionesRep [x] = [[x]]
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]]
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
permutacionesRepN :: Integer -> Integer -> [[Integer]]
permutacionesRepN n k = permutacionesRep (concat [replicate (fromInteger k) t | t<-[1..n]])


-- Álvaro Galisteo:

permutacionesRepN :: Integer -> Integer -> [[Integer]]
permutacionesRepN n k = permutacionesRep (concat [[1..n] | k <- [1..k]])


-- ----------------------------------------------------------------------------
-- 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
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
numeroPermutacionesRepL :: Integer -> Integer -> Integer
numeroPermutacionesRepL n k= fromIntegral (length (permutacionesRepN n k))


-- Álvaro Galisteo:

numeroPermutacionesRepL :: Integer -> Integer -> Integer
numeroPermutacionesRepL n k = fromIntegral(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
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
numeroPermutacionesRepF :: Integer -> Integer -> Integer
numeroPermutacionesRepF n k = div (numeroPermutacionesF (k*n)) ((numeroPermutacionesF k)^n)


-- Álvaro Galisteo: 

numeroPermutacionesRepF :: Integer -> Integer -> Integer
numeroPermutacionesRepF n k = div (product [2..(n*k)]) ((product [2..k])^n)
 

-- ----------------------------------------------------------------------------
-- 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
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
prop_numeroPermutacionesRep :: Integer -> Bool
prop_numeroPermutacionesRep n = and [ numeroPermutacionesRepF n k == numeroPermutacionesRepL n k | k<-[1..n]]


-- Álvaro Galisteo: 

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"]
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
combinaciones :: Integer -> [a] -> [[a]]
combinaciones n xs = filter (\ xs -> length xs == fromIntegral n) (subconjuntos xs)


-- Álvaro Galisteo: 

combinaciones :: Integer -> [a] -> [[a]]
combinaciones k xs = filter (\ xs -> length xs == k') (subconjuntos xs)
                   where k' = fromIntegral k


-- ----------------------------------------------------------------------------
-- 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]]
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
combinacionesN :: Integer -> Integer -> [[Integer]]
combinacionesN k n = combinaciones k [1..n] 


-- Álvaro Galisteo: 

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
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
numeroCombinacionesL :: Integer -> Integer -> Integer
numeroCombinacionesL n k = fromIntegral (length (combinacionesN n k))


-- Álvaro Galisteo: 

numeroCombinacionesL :: Integer -> Integer -> Integer
numeroCombinacionesL k n = fromIntegral(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
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
comb :: Integer -> Integer -> Integer
comb n k = div (numeroPermutacionesF n) ((numeroPermutacionesF (n-k))*(numeroPermutacionesF k))


-- Álvaro Galisteo: 

comb :: Integer -> Integer -> Integer
comb n k = div (product [2..n]) ((product [2..k])*(product [2..(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
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
numeroCombinacionesF :: Integer -> Integer -> Integer
numeroCombinacionesF n k = comb n k


-- Álvaro Galisteo: 

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
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
prop_numeroCombinaciones :: Integer -> Bool
prop_numeroCombinaciones n = and [numeroCombinacionesF n k == numeroCombinacionesL n k | k<-[1..n]]


-- Álvaro Galisteo: 

prop_numeroCombinaciones :: Integer -> Bool
prop_numeroCombinaciones n = and [numeroCombinacionesL x k ==  numeroCombinacionesF x k | 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"]
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n*factorial (n-1)

combinacionesRep :: Integer -> [a] -> [[a]]
combinacionesRep 0 xs = combinaciones 0 xs
combinacionesRep 1 xs = combinaciones 1 xs
combinacionesRep n xs =  concat[map([xs!!k]++) (combinacionesRep (n-1) (drop k xs)) | k<-[0..(length xs) -1]] 


-- Álvaro Galisteo: 

combinacionesRep :: Integer -> [a] -> [[a]]
combinacionesRep _ [] = []
combinacionesRep 0 _  = [[]]
combinacionesRep k (x:xs) = [x:ys | ys <- combinacionesRep (k-1) (x:xs)] ++ combinacionesRep k 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]]
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
combinacionesRepN :: Integer -> Integer -> [[Integer]]
combinacionesRepN k n= combinacionesRep k [1..n] 


-- Álvaro Galisteo: 

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
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
numeroCombinacionesRepL :: Integer -> Integer -> Integer
numeroCombinacionesRepL k n = fromIntegral (length (combinacionesRepN k n))


-- Álvaro Galisteo:

numeroCombinacionesRepL :: Integer -> Integer -> Integer
numeroCombinacionesRepL k n = fromIntegral (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
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
numeroCombinacionesRepF :: Integer -> Integer -> Integer
numeroCombinacionesRepF k n = div (factorial (n+k-1)) ((factorial k)*(factorial (n-1)))


-- Álvaro Galisteo: 

numeroCombinacionesRepF :: Integer -> Integer -> Integer
numeroCombinacionesRepF k n = div (product [2..(n+k-1)]) ((product [2..k])*(product [2..(n-1)]))


-- ----------------------------------------------------------------------------
-- 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
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
prop_numeroCombinacionesRep :: Integer -> Bool
prop_numeroCombinacionesRep n = and [numeroCombinacionesRepF n k == numeroCombinacionesRepL n k | k<-[1..n]]


-- Álvaro Galisteo:

prop_numeroCombinacionesRep :: Integer -> Bool
prop_numeroCombinacionesRep n = and [numeroCombinacionesRepL x k == numeroCombinacionesRepF x k | 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"]
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
variaciones :: Integer -> [a] -> [[a]]
variaciones k xs = concat [permutaciones c | c<-(combinaciones k xs)]


-- Álvaro Galisteo: 

variaciones :: Integer -> [a] -> [[a]]
variaciones k xs = concat (map permutaciones (combinaciones k 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]]
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
variacionesN :: Integer -> Integer -> [[Integer]]
variacionesN k n = variaciones k [1..n]

-- Álvaro Galisteo: 

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
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
numeroVariacionesL :: Integer -> Integer -> Integer
numeroVariacionesL k n = fromIntegral (length (variacionesN k n))


-- Álvaro Galisteo: 

numeroVariacionesL :: Integer -> Integer -> Integer
numeroVariacionesL k n = fromIntegral (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
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
numeroVariacionesF :: Integer -> Integer -> Integer
numeroVariacionesF k n = div (factorial n) (factorial (n-k))


-- Álvaro Galisteo: 

numeroVariacionesF :: Integer -> Integer -> Integer
numeroVariacionesF k n = div (product [2..n]) (product [2..(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
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
prop_numeroVariaciones :: Integer -> Bool
prop_numeroVariaciones n = and [numeroVariacionesF k n == numeroVariacionesL k n | k<-[1..n]]


-- Álvaro Galisteo: 

prop_numeroVariaciones :: Integer -> Bool
prop_numeroVariaciones n = and [numeroVariacionesL x k == numeroVariacionesF x k | 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"]
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
variacionesRep :: Integer -> [a] -> [[a]]
variacionesRep k xs = concat (map (permutacionesRep) (combinacionesRep k xs))


-- Álvaro Galisteo: 

variacionesRep :: Integer -> [a] -> [[a]]
variacionesRep 1 xs = [[x] | x <- xs]
variacionesRep k xs = [zs | x <- xs, zs <- map ([x]++) (variacionesRep (k-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]]
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
variacionesRepN :: Integer -> Integer -> [[Integer]]
variacionesRepN k n= variacionesRep k [1..n]


-- Álvaro Galisteo: 

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
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
numeroVariacionesRepL :: Integer -> Integer -> Integer
numeroVariacionesRepL k n = fromIntegral(length (variacionesRepN k n))


-- Álvaro Galisteo: 

numeroVariacionesRepL :: Integer -> Integer -> Integer
numeroVariacionesRepL k n = fromIntegral (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
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
numeroVariacionesRepF :: Integer -> Integer -> Integer
numeroVariacionesRepF k n = n^k


-- Álvaro Galisteo: 

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
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
prop_numeroVariacionesRep :: Integer -> Bool
prop_numeroVariacionesRep n = and [numeroVariacionesRepL k n == numeroVariacionesRepF k n | k<-[1..n]]


-- Álvaro Galisteo: 

prop_numeroVariacionesRep :: Integer -> Bool
prop_numeroVariacionesRep n = and [numeroVariacionesRepL x k == numeroVariacionesRepF x k | x <- [1..n] , k <- [1..x]]


-- ============================================================================