Clase 08 - Taller Álgebra I

clase_08.hs

type Set a = [a]

esVacio :: Set a -> Bool
esVacio [] = True
esVacio (x:xs) = False

agregar :: Integer -> Set Integer -> Set Integer
agregar x xs | elem x xs = xs
             | otherwise = x:xs

incluido :: Eq a => Set a -> Set a -> Bool
incluido [] _ = True
incluido (x:xs) ys = elem x ys && incluido xs ys

iguales :: Eq a => Set a -> Set a -> Bool
iguales as bs = incluido as bs && incluido bs as


agregarATodas :: a -> [[a]] -> [[a]]
agregarATodas _ [] = []
agregarATodas x (ls:lls) = (x:ls):agregarATodas x lls

partes :: Eq a => Set a -> Set ( Set a)
partes [] = [[]]
partes (x:xs) = agregarATodas x (partes xs) ++ partes xs

subconjuntos :: Integer -> Integer -> Set (Set Integer)
subconjuntos 0 0 = [[]]
subconjuntos 0 _ = [[]]
subconjuntos _ 0 = []
subconjuntos k n = subconjuntos k (n-1) ++ agregarATodas n (subconjuntos (k-1) (n-1))


productoCartesiano:: Set Integer -> Set Integer -> Set (Integer, Integer)
productoCartesiano [] _ = []
productoCartesiano (x:xs) ys = tuplas x ys ++ productoCartesiano xs ys

-- Devuelve, dado x e
tuplas :: Integer -> Set Integer -> Set(Integer, Integer)
tuplas x [] = []
tuplas x (y:ys) = (x,y):tuplas x ys

comoLista :: Set Integer -> [[Integer]]
comoLista [] = []
comoLista (x:xs) = [x]:comoLista xs

agregarATodasListas:: [Integer] -> [[Integer]] -> [[Integer]]
agregarATodasListas [] _ = []
agregarATodasListas (x:xs) ys = agregarATodas x ys ++ agregarATodasListas xs ys

variaciones :: Set Integer -> Integer -> [[Integer]]
variaciones xs 0 = [[]]
variaciones xs n = agregarATodasListas xs (variaciones xs (n-1))

insertarEn:: [Integer] -> Integer -> Integer -> [Integer]
insertarEn ys x 1 = x:ys
insertarEn (y:ys) x n | n > 1 = y:insertarEn ys x (n-1)

permutaciones :: Integer -> [[Integer]]
permutaciones 1 = [[1]]
permutaciones n = agregarEnCadaPosicion [1..n] n (permutaciones (n-1))

agregarEnCadaPosicion :: [Integer] -> Integer -> [[Integer]] -> [[Integer]]
agregarEnCadaPosicion [] _ _ = []
agregarEnCadaPosicion (i:is) x ps = agregarATodasListasEnPosicion i x ps ++ agregarEnCadaPosicion is x ps

agregarATodasListasEnPosicion:: Integer -> Integer -> [[Integer]] -> [[Integer]]
agregarATodasListasEnPosicion i x [] = []
agregarATodasListasEnPosicion i x (ls:lls) = (insertarEn ls x i):(agregarATodasListasEnPosicion i x lls)

----

bolitasEnCajasOrdenadas :: Integer -> Integer -> Integer
bolitasEnCajasOrdenadas n k = variaciones [1..k] n

listasNumerosDistintos :: Integer -> Integer -> [[Integer]]
listasNumerosDistintos n k = filtrarOrdenados(variaciones [1..n] k)

filtrarOrdenados :: [[Integer]] -> [[Integer]]
filtrarOrdenados [] = []
filtrarOrdenados (ls:lls) | estaOrdenado ls = ls:filtrarOrdenados lls
                          | otherwise = filtrarOrdenados lls

estaOrdenado :: [Integer] -> Bool
estaOrdenado [] = True
estaOrdenado (x:[]) = True
estaOrdenado (x:xs) = x < (minimo xs) && estaOrdenado xs

minimo :: [Integer] -> Integer
minimo (x:[]) = x
minimo (x:xs) | x < minimo xs = x
              | otherwise = minimo xs