Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. Número de particiones en k subconjuntos
- 2. Composición de relaciones binarias
- 3. Transitividad de una relación
- 4. Clausura transitiva de una relación binaria
- 5. Primos cubanos
A continuación se muestran las soluciones.
1. Número de particiones en k subconjuntos
Definir la función
numeroParticiones :: Int -> Int -> Int |
tal que (numeroParticiones n k) es el número de particiones de conjunto de n elementos en k subconjuntos disjuntos. Por ejemplo,
numeroParticiones 3 2 == 3 numeroParticiones 3 3 == 1 numeroParticiones 4 3 == 6 numeroParticiones 4 1 == 1 numeroParticiones 4 4 == 1 numeroParticiones 91 89 == 8139495 |
Soluciones
import Data.Array (Array, (!), array) import Test.QuickCheck (Positive (Positive), quickCheckWith) -- 1ª solución -- =========== numeroParticiones1 :: Int -> Int -> Int numeroParticiones1 n k = length (particiones1 [1..n] k) particiones1 :: [a] -> Int -> [[[a]]] particiones1 [] _ = [] particiones1 _ 0 = [] particiones1 xs 1 = [[xs]] particiones1 (x:xs) k = [[x]:ys | ys <- particiones1 xs (k-1)] ++ concat [inserta x ys | ys <- particiones1 xs k] -- (inserta x yss) es la lista obtenida insertando x en cada uno de los -- conjuntos de yss. Por ejemplo, -- inserta 4 [[3],[2,5]] == [[[4,3],[2,5]],[[3],[4,2,5]]] inserta :: a -> [[a]] -> [[[a]]] inserta _ [] = [] inserta x (ys:yss) = ((x:ys):yss) : [ys:zss | zss <- inserta x yss] -- 2ª solución -- =========== numeroParticiones2 :: Int -> Int -> Int numeroParticiones2 0 _ = 0 numeroParticiones2 _ 0 = 0 numeroParticiones2 _ 1 = 1 numeroParticiones2 n k = k * numeroParticiones2 (n-1) k + numeroParticiones2 (n-1) (k-1) -- 3ª solución -- =========== numeroParticiones3 :: Int -> Int -> Int numeroParticiones3 n k = matrizNumeroParticiones n k ! (n,k) matrizNumeroParticiones :: Int -> Int -> Array (Int,Int) Int matrizNumeroParticiones n k = q where q = array ((0,0),(n,k)) [((i,j), f i j) | i <- [0..n], j <- [0..k]] f _ 0 = 0 f 0 _ = 0 f _ 1 = 1 f i j | i == j = 1 | otherwise = j * f (i-1) j + f (i-1) (j-1) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_numeroParticiones :: Positive Int -> Positive Int -> Bool prop_numeroParticiones (Positive n) (Positive k) = all (== numeroParticiones1 n k) [numeroParticiones2 n k, numeroParticiones3 n k] -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=10}) prop_numeroParticiones -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> numeroParticiones1 12 6 -- 1323652 -- (1.22 secs, 1,152,945,608 bytes) -- λ> numeroParticiones2 12 6 -- 1323652 -- (0.00 secs, 1,283,152 bytes) -- λ> numeroParticiones3 12 6 -- 1323652 -- (0.01 secs, 1,155,864 bytes) -- -- λ> numeroParticiones2 21 19 -- 19285 -- (2.04 secs, 990,274,976 bytes) -- λ> numeroParticiones3 21 19 -- 19285 -- (0.00 secs, 940,736 bytes) |
El código se encuentra en GitHub.
2. Composición de relaciones binarias
Las relaciones binarias en un conjunto A se pueden representar mediante conjuntos de pares de elementos de A. Por ejemplo, la relación de divisibilidad en el conjunto {1,2,3,6} se representa por
[(1,1),(1,2),(1,3),(1,6),(2,2),(2,6),(3,3),(3,6),(6,6)] |
La composición de dos relaciones binarias R y S en el conjunto A es la relación binaria formada por los pares (x,y) para los que existe un z tal que (x,z) ∈ R y (z,y) ∈ S.
Definir la función
composicion :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)] |
tal que (composicion r s) es la composición de las relaciones binarias r y s. Por ejemplo,
λ> composicion [(1,2)] [(2,3),(2,4)] [(1,3),(1,4)] λ> composicion [(1,2),(5,2)] [(2,3),(2,4)] [(1,3),(1,4),(5,3),(5,4)] λ> composicion [(1,2),(1,4),(1,5)] [(2,3),(4,3)] [(1,3)] |
Nota: Se supone que las relaciones binarias son listas sin elementos repetidos.
Soluciones
import Data.List (nub, sort) import Data.Maybe (mapMaybe) import qualified Data.Set.Monad as S (Set, fromList, toList) import qualified Data.Map as M (Map, assocs, empty, insertWith, lookup, map) import Test.QuickCheck (quickCheck) -- 1ª solución -- =========== composicion1 :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)] composicion1 r s = nub [(x,y) | (x,u) <- r, (v,y) <- s, u == v] -- 2ª solución -- =========== composicion2 :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)] composicion2 r s = S.toList (composicionS (S.fromList r) (S.fromList s)) composicionS :: Ord a => S.Set (a,a) -> S.Set (a,a) -> S.Set (a,a) composicionS r s = [(x,y) | (x,u) <- r, (v,y) <- s, u == v] -- 3ª solución -- =========== composicion3 :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)] composicion3 r s = relAlista (composicionRel (listaArel r) (listaArel s)) -- Una relación se puede representar por un diccionario donde las claves -- son los elementos y los valores son las listas de los elementos con -- los que se relaciona. type Rel a = M.Map a [a] -- (listaArel xys) es la relación correspondiente a la lista de pares -- xys. Por ejemplo. -- λ> listaArel [(1,1),(1,2),(1,3),(1,6),(2,2),(2,6),(3,3),(3,6),(6,6)] -- fromList [(1,[1,2,3,6]),(2,[2,6]),(3,[3,6]),(6,[6])] listaArel :: Ord a => [(a,a)] -> Rel a listaArel [] = M.empty listaArel ((x,y):xys) = M.insertWith (++) x [y] (listaArel xys) -- (composicionRel r s) es la composición de las relaciones r y s. Por -- ejemplo, -- λ> r = listaArel [(1,2),(5,2)] -- λ> s = listaArel [(2,3),(2,4)] -- λ> composicionRel r s -- fromList [(1,[3,4]),(5,[3,4])] composicionRel :: Ord a => Rel a -> Rel a -> Rel a composicionRel r s = M.map f r where f xs = concat (mapMaybe (`M.lookup` s) xs) -- (relAlista r) es la lista de pares correspondientes a la relación -- r. Por ejemplo, -- λ> relAlista (M.fromList [(1,[3,4]),(5,[3,4])]) -- [(1,3),(1,4),(5,3),(5,4)] relAlista :: Ord a => Rel a -> [(a,a)] relAlista r = nub [(x,y) | (x,ys) <- M.assocs r, y <- ys] -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_composicion :: [(Int,Int)] -> [(Int,Int)] -> Bool prop_composicion r s = all (== sort (composicion1 r' s')) [sort (composicion2 r' s'), sort (composicion3 r' s')] where r' = nub r s' = nub s -- La comprobación es -- λ> quickCheck prop_composicion -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (composicion1 [(n,n+1) | n <- [1..2000]] [(n,n+1) | n <- [1..2000]]) -- 1999 -- (1.54 secs, 770,410,352 bytes) -- λ> length (composicion2 [(n,n+1) | n <- [1..2000]] [(n,n+1) | n <- [1..2000]]) -- 1999 -- (1.66 secs, 1,348,948,096 bytes) -- λ> length (composicion3 [(n,n+1) | n <- [1..2000]] [(n,n+1) | n <- [1..2000]]) -- 1999 -- (0.07 secs, 6,960,552 bytes) -- -- λ> r100 = [(n,k) | n <- [1..100], k <- [1..n]] -- λ> length (composicion1 r100 r100) -- 5050 -- (9.91 secs, 4,946,556,944 bytes) -- λ> length (composicion2 r100 r100) -- 5050 -- (13.59 secs, 15,241,357,536 bytes) -- λ> length (composicion3 r100 r100) -- 5050 -- (0.35 secs, 52,015,544 bytes) |
El código se encuentra en GitHub.
3. Transitividad de una relación
Una relación binaria R sobre un conjunto A es transitiva cuando se cumple que siempre que un elemento se relaciona con otro y éste último con un tercero, entonces el primero se relaciona con el tercero.
Definir la función
transitiva :: Ord a => [(a,a)] -> Bool |
tal que (transitiva r) se verifica si la relación r es transitiva. Por ejemplo,
transitiva [(1,1),(1,3),(3,1),(3,3),(5,5)] == True transitiva [(1,1),(1,3),(3,1),(5,5)] == False transitiva [(n,n) | n <- [1..10^4]] == True |
Soluciones
import Data.List (nub) import Data.Maybe (mapMaybe) import qualified Data.Map as M (Map, assocs, empty, insertWith, lookup, map) import Test.QuickCheck (maxSize, quickCheckWith, stdArgs) -- 1ª solución -- =========== transitiva1 :: Ord a => [(a,a)] -> Bool transitiva1 r = and [(x,y) `elem` r | (x,u) <- r, (v,y) <- r, u == v] -- 2ª solución -- =========== transitiva2 :: Ord a => [(a,a)] -> Bool transitiva2 r = all (`elem` r) [(x,y) | (x,u) <- r, (v,y) <- r, u == v] -- 3ª solución -- =========== transitiva3 :: Ord a => [(a,a)] -> Bool transitiva3 r = subconjunto (composicion r r) r -- (subconjunto xs ys) se verifica si xs es un subconjunto de xs. Por -- ejemplo, -- subconjunto [1,3] [3,1,5] == True -- subconjunto [3,1,5] [1,3] == False subconjunto :: Ord a => [a] -> [a] -> Bool subconjunto xs ys = all (`elem`ys) xs -- (composicion r s) es la composición de las relaciones binarias r y -- s. Por ejemplo, -- λ> composicion [(1,2)] [(2,3),(2,4)] -- [(1,3),(1,4)] -- λ> composicion [(1,2),(5,2)] [(2,3),(2,4)] -- [(1,3),(1,4),(5,3),(5,4)] -- λ> composicion [(1,2),(1,4),(1,5)] [(2,3),(4,3)] -- [(1,3)] composicion :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)] composicion r s = nub [(x,y) | (x,u) <- r, (v,y) <- s, u == v] -- 3ª solución -- =========== transitiva4 :: Ord a => [(a,a)] -> Bool transitiva4 r = subconjunto (composicion4 r r) r composicion4 :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)] composicion4 r s = relAlista (composicionRel (listaArel r) (listaArel s)) -- Una relación se puede representar por un diccionario donde las claves -- son los elementos y los valores son las listas de los elementos con -- los que se relaciona. type Rel a = M.Map a [a] -- (listaArel xys) es la relación correspondiente a la lista de pares -- xys. Por ejemplo. -- λ> listaArel [(1,1),(1,2),(1,3),(1,6),(2,2),(2,6),(3,3),(3,6),(6,6)] -- fromList [(1,[1,2,3,6]),(2,[2,6]),(3,[3,6]),(6,[6])] listaArel :: Ord a => [(a,a)] -> Rel a listaArel [] = M.empty listaArel ((x,y):xys) = M.insertWith (++) x [y] (listaArel xys) -- (composicionRel r s) es la composición de las relaciones r y s. Por -- ejemplo, -- λ> r = listaArel [(1,2),(5,2)] -- λ> s = listaArel [(2,3),(2,4)] -- λ> composicionRel r s -- fromList [(1,[3,4]),(5,[3,4])] composicionRel :: Ord a => Rel a -> Rel a -> Rel a composicionRel r s = M.map f r where f xs = concat (mapMaybe (`M.lookup` s) xs) -- (relAlista r) es la lista de pares correspondientes a la relación -- r. Por ejemplo, -- λ> relAlista (M.fromList [(1,[3,4]),(5,[3,4])]) -- [(1,3),(1,4),(5,3),(5,4)] relAlista :: Ord a => Rel a -> [(a,a)] relAlista r = nub [(x,y) | (x,ys) <- M.assocs r, y <- ys] -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_transitiva :: [(Int,Int)] -> Bool prop_transitiva r = all (== transitiva1 r) [transitiva2 r, transitiva3 r, transitiva4 r] -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=7}) prop_transitiva -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> transitiva1 [(n,n) | n <- [1..5*10^3]] -- True -- (4.27 secs, 1,403,139,032 bytes) -- λ> transitiva2 [(n,n) | n <- [1..5*10^3]] -- True -- (4.24 secs, 1,402,739,056 bytes) -- λ> transitiva3 [(n,n) | n <- [1..5*10^3]] -- True -- (4.41 secs, 1,403,219,880 bytes) -- λ> transitiva4 [(n,n) | n <- [1..5*10^3]] -- True -- (0.46 secs, 16,206,624 bytes) |
El código se encuentra en GitHub.
4. Clausura transitiva de una relación binaria
La clausura transitiva de una relación binaria R es la relación transitiva que contiene a R. Se puede calcular
usando la composición de relaciones. Veamos un ejemplo, en el que (R ∘ S) representa la composición de R y S: sea
R = [(1,2),(2,5),(5,6)] |
la relación R no es transitiva ya que (1,2) y (1,5) pertenecen a R pero (1,5) no pertenece; sea
R1 = R ∪ (R ∘ R)
= [(1,2),(2,5),(5,6),(1,5),(2,6)] |
la relación R1 tampoco es transitiva ya que (1,2) y (2,6) pertenecen a R pero (1,6) no pertenece; sea
R2 = R1 ∪ (R1 ∘ R1)
= [(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)] |
La relación R2 es transitiva y contiene a R. Además, R2 es la clausura transitiva de R.
Definir la función
clausuraTransitiva :: Ord a => [(a,a)] -> [(a,a)] |
tal que (clausuraTransitiva r) es la clausura transitiva de r; es decir, la menor relación transitiva que contiene a r. Por ejemplo,
λ> clausuraTransitiva [(1,2),(2,5),(5,6)] [(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)] λ> clausuraTransitiva [(1,2),(2,5),(5,6),(6,3)] [(1,2),(2,5),(5,6),(6,3),(1,5),(2,6),(5,3),(1,6),(2,3),(1,3)] λ> length (clausuraTransitiva [(n,n+1) | n <- [1..100]]) 5050 |
Soluciones
import Data.List (union, nub, sort) import Data.Maybe (mapMaybe) import qualified Data.Map as M (Map, assocs, empty, insertWith, lookup, map) import Test.QuickCheck (quickCheck) -- 1ª solución -- =========== clausuraTransitiva1 :: Ord a => [(a,a)] -> [(a,a)] clausuraTransitiva1 r | transitiva r = r | otherwise = clausuraTransitiva1 r1 where r1 = r `union` composicion r r -- (transitiva r) se verifica si la relación r es transitiva. Por -- ejemplo, -- transitiva [(1,1),(1,3),(3,1),(3,3),(5,5)] == True -- transitiva [(1,1),(1,3),(3,1),(5,5)] == False transitiva :: Ord a => [(a,a)] -> Bool transitiva r = subconjunto (composicion r r) r -- (composicion r s) es la composición de las relaciones binarias r y -- s. Por ejemplo, -- λ> composicion [(1,2)] [(2,3),(2,4)] -- [(1,3),(1,4)] -- λ> composicion [(1,2),(5,2)] [(2,3),(2,4)] -- [(1,3),(1,4),(5,3),(5,4)] -- λ> composicion [(1,2),(1,4),(1,5)] [(2,3),(4,3)] -- [(1,3)] composicion :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)] composicion r s = nub [(x,y) | (x,u) <- r, (v,y) <- s, u == v] -- (subconjunto xs ys) se verifica si xs es un subconjunto de xs. Por -- ejemplo, -- subconjunto [1,3] [3,1,5] == True -- subconjunto [3,1,5] [1,3] == False subconjunto :: Ord a => [a] -> [a] -> Bool subconjunto xs ys = all (`elem` ys) xs -- 2ª solución -- ============= clausuraTransitiva2 :: Ord a => [(a,a)] -> [(a,a)] clausuraTransitiva2 r | r1 == r = r | otherwise = clausuraTransitiva2 r1 where r1 = r `union` composicion r r -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_clausuraTransitiva :: [(Int,Int)] -> Bool prop_clausuraTransitiva r = all (== sort (clausuraTransitiva1 r)) [sort (clausuraTransitiva2 r), sort (clausuraTransitiva3 r)] -- La comprobación es -- λ> quickCheck prop_clausuraTransitiva -- +++ OK, passed 100 tests. -- 3ª solución -- =========== clausuraTransitiva3 :: Ord a => [(a,a)] -> [(a,a)] clausuraTransitiva3 r | transitiva3 r = r | otherwise = clausuraTransitiva3 r1 where r1 = r `union` composicion3 r r transitiva3 :: Ord a => [(a,a)] -> Bool transitiva3 r = subconjunto (composicion3 r r) r composicion3 :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)] composicion3 r s = relAlista (composicionRel (listaArel r) (listaArel s)) -- Una relación se puede representar por un diccionario donde las claves -- son los elementos y los valores son las listas de los elementos con -- los que se relaciona. type Rel a = M.Map a [a] -- (listaArel xys) es la relación correspondiente a la lista de pares -- xys. Por ejemplo. -- λ> listaArel [(1,1),(1,2),(1,3),(1,6),(2,2),(2,6),(3,3),(3,6),(6,6)] -- fromList [(1,[1,2,3,6]),(2,[2,6]),(3,[3,6]),(6,[6])] listaArel :: Ord a => [(a,a)] -> Rel a listaArel [] = M.empty listaArel ((x,y):xys) = M.insertWith (++) x [y] (listaArel xys) -- (composicionRel r s) es la composición de las relaciones r y s. Por -- ejemplo, -- λ> r = listaArel [(1,2),(5,2)] -- λ> s = listaArel [(2,3),(2,4)] -- λ> composicionRel r s -- fromList [(1,[3,4]),(5,[3,4])] composicionRel :: Ord a => Rel a -> Rel a -> Rel a composicionRel r s = M.map f r where f xs = concat (mapMaybe (`M.lookup` s) xs) -- (relAlista r) es la lista de pares correspondientes a la relación -- r. Por ejemplo, -- λ> relAlista (M.fromList [(1,[3,4]),(5,[3,4])]) -- [(1,3),(1,4),(5,3),(5,4)] relAlista :: Ord a => Rel a -> [(a,a)] relAlista r = nub [(x,y) | (x,ys) <- M.assocs r, y <- ys] -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (clausuraTransitiva1 [(n,n+1) | n <- [1..60]]) -- 1830 -- (2.15 secs, 453,533,992 bytes) -- λ> length (clausuraTransitiva2 [(n,n+1) | n <- [1..60]]) -- 1830 -- (2.23 secs, 558,571,904 bytes) -- λ> length (clausuraTransitiva3 [(n,n+1) | n <- [1..60]]) -- 1830 -- (0.25 secs, 207,168,552 bytes) |
El código se encuentra en GitHub.
5. Primos cubanos
Un primo cubano es un número primo que se puede escribir como diferencia de dos cubos consecutivos. Por ejemplo, el 61 es un primo cubano porque es primo y 61 = 5³-4³.
Definir la sucesión
cubanos :: [Integer] |
tal que sus elementos son los números cubanos. Por ejemplo,
λ> take 15 cubanos [7,19,37,61,127,271,331,397,547,631,919,1657,1801,1951,2269] |
Soluciones
import Data.Numbers.Primes (isPrime) import Test.QuickCheck -- 1ª solución -- =========== cubanos1 :: [Integer] cubanos1 = filter isPrime (zipWith (-) (tail cubos) cubos) -- cubos es la lista de los cubos. Por ejemplo, -- λ> take 10 cubos -- [1,8,27,64,125,216,343,512,729,1000] cubos :: [Integer] cubos = map (^3) [1..] -- 2ª solución -- =========== cubanos2 :: [Integer] cubanos2 = filter isPrime [(x+1)^3 - x^3 | x <- [1..]] -- 3ª solución -- =========== cubanos3 :: [Integer] cubanos3 = filter isPrime [3*x^2 + 3*x + 1 | x <- [1..]] -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_cubanos :: NonNegative Int -> Bool prop_cubanos (NonNegative n) = all (== cubanos1 !! n) [cubanos2 !! n, cubanos3 !! n] -- La comprobación es -- λ> quickCheck prop_cubanos -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> cubanos1 !! 3000 -- 795066361 -- (4.21 secs, 16,953,612,192 bytes) -- λ> cubanos2 !! 3000 -- 795066361 -- (4.27 secs, 16,962,597,288 bytes) -- λ> cubanos3 !! 3000 -- 795066361 -- (4.29 secs, 16,956,085,672 bytes) |
El código se encuentra en GitHub.