Reconocimiento de particiones
Una partición de un conjunto es una división del mismo en subconjuntos disjuntos no vacíos.
Definir la función
|
1 |
esParticion :: Eq a => [[a]] -> Bool |
tal que (esParticion xss) se verifica si xss es una partición; es decir sus elementos son listas no vacías disjuntas. Por ejemplo.
|
1 2 3 4 |
esParticion [[1,3],[2],[9,5,7]] == True esParticion [[1,3],[2],[9,5,1]] == False esParticion [[1,3],[],[9,5,7]] == False esParticion [[2,3,2],[4]] == True |
Soluciones
|
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 |
import Data.List ((\\), intersect) -- 1ª definición -- ============= esParticion :: Eq a => [[a]] -> Bool esParticion xss = [] `notElem` xss && and [disjuntos xs ys | xs <- xss, ys <- xss \\ [xs]] disjuntos :: Eq a => [a] -> [a] -> Bool disjuntos xs ys = null (xs `intersect` ys) -- 2ª definición -- ============= esParticion2 :: Eq a => [[a]] -> Bool esParticion2 [] = True esParticion2 (xs:xss) = not (null xs) && and [disjuntos xs ys | ys <- xss] && esParticion2 xss -- 3ª definición -- ============= esParticion3 :: Eq a => [[a]] -> Bool esParticion3 [] = True esParticion3 (xs:xss) = not (null xs) && all (disjuntos xs) xss && esParticion3 xss -- Equivalencia prop_equiv :: [[Int]] -> Bool prop_equiv xss = and [esParticion xss == f xss | f <- [ esParticion2 , esParticion3]] -- Comprobación -- λ> quickCheck prop_equiv -- +++ OK, passed 100 tests. -- Comparación de eficiencia: -- λ> esParticion [[x] | x <- [1..3000]] -- True -- (4.37 secs, 3,527,956,400 bytes) -- λ> esParticion2 [[x] | x <- [1..3000]] -- True -- (1.26 secs, 1,045,792,552 bytes) -- λ> esParticion3 [[x] | x <- [1..3000]] -- True -- (1.30 secs, 1,045,795,272 bytes) -- λ> esParticion3 [[x] | x <- [1..3000]] -- True -- (1.30 secs, 1,045,795,272 bytes) |
Pensamiento
Sentía los cuatro vientos,
en la encrucijada
de su pensamiento.Antonio Machado