Menu Close

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

   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.

   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

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

3 soluciones de “Reconocimiento de particiones

  1. luipromor
    import Data.List (intersect)
     
    esParticion :: Eq a => [[a]] -> Bool
    esParticion []   = True
    esParticion [xs] = xs /= []
    esParticion (xs:ys:xss) =
      null (intersect xs ys) &&
      esParticion (xs:xss) &&
      esParticion (ys:xss) &&
      (not . null) xs
  2. frahidzam
    esParticion :: Eq a => [[a]] -> Bool
    esParticion xss
      | elem [] xss                                                  = False
      | and [intersect xs ys == [] | xs <- xss, ys <- xss, xs /= ys] = True
      | otherwise                                                    = False
  3. lucsanand
    import Data.List (nub)
     
    esParticion :: Eq a => [[a]] -> Bool
    esParticion xss
      | elem [] xss = False
      | otherwise   = nub (listaDeListas xss) == listaDeListas xss
     
    listaDeListas :: Eq a => [[a]] -> [a]
    listaDeListas []       = []
    listaDeListas (xs:xss) = nub xs ++ listaDeListas xss

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.