Menu Close

Árbol de subconjuntos

Se dice que A es un subconjunto maximal de B si A ⊂ B y no existe ningún C tal que A ⊂ C y C ⊂ B. Por ejemplo, {2,5} es un subconjunto maximal de {2,3,5], pero {3] no lo es.

El árbol de los subconjuntos de un conjunto A es el árbol que tiene como raíz el conjunto A y cada nodo tiene como hijos sus subconjuntos maximales. Por ejemplo, el árbol de subconjuntos de [2,3,5] es

          [2, 3, 5]
          /   |  \
         /    |   \  
        /     |    \   
       /      |     \
      /       |      \
    [5,3]   [2,3]   [2,5]  
    /  \    /  \    /  \  
   [3] [5] [3] [2] [5] [2]
    |   |   |   |   |   | 
   [ ] [ ] [ ] [ ] [ ] [ ]

Usando el tipo de dato

   data Arbol = N [Integer] [Arbol]
     deriving (Eq, Show)

el árbol anterior se representa por

   N [2,5,3]
     [N [5,3]
        [N [3]
           [N [] []],
         N [5]
           [N [] []]],
      N [2,3]
        [N [3]
           [N [] []],
         N [2]
           [N [] []]],
      N [2,5]
        [N [5]
           [N [] []],
         N [2]
           [N [] []]]]

Definir las funciones

   arbolSubconjuntos :: [Int] -> Arbol 
   nOcurrenciasArbolSubconjuntos :: [Int] -> [Int] -> Int

tales que

  • (arbolSubconjuntos x) es el árbol de los subconjuntos de xs. Por ejemplo,
     λ> arbolSubconjuntos [2,5,3]
     N [2,5,3] [N [5,3] [N [3] [N [] []],N [5] [N [] []]],
                N [2,3] [N [3] [N [] []],N [2] [N [] []]],
                N [2,5] [N [5] [N [] []],N [2] [N [] []]]]
  • (nOcurrenciasArbolSubconjuntos xs ys) es el número de veces que aparece el conjunto xs en el árbol de los subconjuntos de ys. Por ejemplo,
     nOcurrenciasArbolSubconjuntos []      [2,5,3]  ==  6
     nOcurrenciasArbolSubconjuntos [3]     [2,5,3]  ==  2
     nOcurrenciasArbolSubconjuntos [3,5]   [2,5,3]  ==  1
     nOcurrenciasArbolSubconjuntos [3,5,2] [2,5,3]  ==  1

Comprobar con QuickChek que, para todo entero positivo n, el número de ocurrencia de un subconjunto xs de [1..n] en el árbol de los subconjuntos de [1..n] es el factorial de n-k (donde k es el número de elementos de xs).

Soluciones

import Data.List (delete, nub, sort, subsequences)
import Test.QuickCheck
 
data Arbol = N [Int] [Arbol]
  deriving (Eq, Show)
 
arbolSubconjuntos :: [Int] -> Arbol 
arbolSubconjuntos xs =
  N xs (map arbolSubconjuntos (subconjuntosMaximales xs))
 
-- (subconjuntosMaximales xs) es la lista de los subconjuntos maximales
-- de xs. Por ejemplo,
--    subconjuntosMaximales [2,5,3]  ==  [[5,3],[2,3],[2,5]]
subconjuntosMaximales :: [Int] -> [[Int]]
subconjuntosMaximales xs =
  [delete x xs | x <- xs]
 
-- Definición de nOcurrenciasArbolSubconjuntos
-- ===========================================
 
nOcurrenciasArbolSubconjuntos :: [Int] -> [Int] -> Int
nOcurrenciasArbolSubconjuntos xs ys =
  nOcurrencias xs (arbolSubconjuntos ys)
 
-- (nOcurrencias x a) es el número de veces que aparece x en el árbol
-- a. Por ejemplo,
--    nOcurrencias 3 (arbolSubconjuntos 30)  ==  2
nOcurrencias :: [Int] -> Arbol -> Int
nOcurrencias xs (N ys [])
  | conjunto xs == conjunto ys  = 1
  | otherwise                   = 0
nOcurrencias xs (N ys zs)
  | conjunto xs == conjunto ys = 1 + sum [nOcurrencias xs z | z <- zs]
  | otherwise                  = sum [nOcurrencias xs z | z <- zs]
 
-- (conjunto xs) es el conjunto ordenado correspondiente a xs. Por
-- ejemplo, 
--    conjunto [3,2,5,2,3,7,2]  ==  [2,3,5,7]
conjunto :: [Int] -> [Int]
conjunto = nub . sort
 
-- La propiedad es
prop_nOcurrencias :: (Positive Int) -> [Int] -> Bool
prop_nOcurrencias (Positive n) xs =
  nOcurrenciasArbolSubconjuntos ys [1..n] == factorial (n-k)
  where ys = nub [1 + x `mod` n | x <- xs]
        k  = length ys
        factorial m = product [1..m]
 
-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=9}) prop_nOcurrencias
--    +++ OK, passed 100 tests.

Pensamiento

Nunca traces tu frontera,
ni cuides de tu perfil;
todo eso es cosa de fuera.

Antonio Machado

5 soluciones de “Árbol de subconjuntos

  1. frahidzam
    import Data.List
    import Test.QuickCheck
     
    data Arbol = N [Int] [Arbol]
         deriving (Eq, Show)
     
    arbolSubconjuntos :: [Int] -> Arbol
    arbolSubconjuntos xs =
      N xs (map arbolSubconjuntos (subconjuntosMaximales xs))
     
    subconjuntosMaximales :: [Int] -> [[Int]]
    subconjuntosMaximales xs =
      [as | as <- reverse (subsequences xs)
          , length as == length xs - 1]
     
    nOcurrenciasArbolSubconjuntos :: [Int] -> [Int] -> Int
    nOcurrenciasArbolSubconjuntos n xs =
      nOcurrencias n (arbolSubconjuntos xs)
     
    nOcurrencias :: [Int] -> Arbol -> Int
    nOcurrencias xs (N ys [])
      | iguales xs ys = 1
      | otherwise     = 0
    nOcurrencias xs (N ys zss)
      | iguales xs ys = 1 + sum [nOcurrencias xs zs | zs <- zss]
      | otherwise     = sum [nOcurrencias xs zs | zs <- zss]
     
    subconjunto :: Eq a => [a] -> [a] -> Bool
    subconjunto xs ys = and [elem x ys | x <- xs]
     
    iguales :: Eq a => [a] -> [a] -> Bool
    iguales xs ys = subconjunto xs ys &&  subconjunto ys xs
     
    prop_nOcurrenciasArbolSubconjuntos :: Int -> Int -> Property
    prop_nOcurrenciasArbolSubconjuntos k n =
      k < n && k > 0 && n > 0 ==>
       nOcurrenciasArbolSubconjuntos [1..k] [1..n] == factorial (n-k)     
     
    factorial :: Int -> Int
    factorial n = product [1..n]
     
    -- La comprobación es:
    -- λ> quickCheckWith (stdArgs {maxSize=8}) prop_nOcurrenciasArbolSubconjuntos
    -- *** Gave up! Passed only 60 tests.
  2. ireprirod
    import Data.List
    import Test.QuickCheck
     
    data Arbol = N [Int] [Arbol]
         deriving (Eq, Show)
     
    arbolSubconjuntos :: [Int] -> Arbol
    arbolSubconjuntos xs =
      N xs [arbolSubconjuntos ys | ys <- subconjuntosMaximales xs]
     
    subconjuntosMaximales :: [Int] -> [[Int]]
    subconjuntosMaximales xs = filter f (subsequences xs)
      where f ys = length ys == length xs-1
     
    nOcurrenciasArbolSubconjuntos :: [Int] -> [Int] -> Int
    nOcurrenciasArbolSubconjuntos xs =
      length . filter (igual xs) . (pliega . arbolSubconjuntos)
     
    pliega :: Arbol -> [[Int]]
    pliega (N [] []) = [[]]
    pliega (N xs ys) = xs : concat (map pliega ys)
     
    igual :: [Int] -> [Int] -> Bool
    igual xs ys = sort xs == sort ys
     
    prop_ocurrencias :: Int -> Int -> Bool
    prop_ocurrencias k n =
       nOcurrenciasArbolSubconjuntos [1..a] [1..b] == product [1..b-a]
       where a = min (abs k) (abs n)
             b = max (abs k) (abs n)
  3. luipromor
    import Data.List (subsequences)
     
    arbolSubconjuntos :: [Int] -> Arbol
    arbolSubconjuntos xs =
      N xs [arbolSubconjuntos ys | ys <- subsequences xs
                                   , length ys == length xs - 1]
    arbolSubconjuntos [_] = N [] []
     
    nOcurrenciasArbolSubconjuntos :: [Int] -> [Int] -> Int
    nOcurrenciasArbolSubconjuntos xs ys =
      aux xs (arbolSubconjuntos ys)
      where aux xs (N zs xss)
              | iguales xs zs = 1 + sum [aux xs os | os <- xss]
              | otherwise     =     sum [aux xs os | os <- xss]
            aux xs (N [] [] )
              | null xs   = 1
              | otherwise = 0
            contenido xs ys = and [elem x ys | x <- xs]
            iguales xs ys = contenido xs ys &&  contenido ys xs
     
    prop_arbolSubconjuntos :: Int -> [Int] -> Property
    prop_arbolSubconjuntos n xs  =
      n > 0 && contenido xs [1..n] && nub xs == xs ==>
      nOcurrenciasArbolSubconjuntos xs [1..n] == product[1..n - length xs]
      where contenido xs ys = and [elem x ys | x <- xs]
  4. lucsanand
    import Data.List (subsequences)
    import Test.QuickCheck
     
    data Arbol = N [Int] [Arbol]
      deriving (Eq, Show)
     
    arbolSubconjuntos :: [Int] -> Arbol
    arbolSubconjuntos xs =
      N xs [arbolSubconjuntos ys | ys <- subconjuntosMaximales xs]
     
    subconjuntosMaximales :: [Int] -> [[Int]]
    subconjuntosMaximales xs =
      [ys | ys <- subsequences xs, length ys == length xs - 1]
     
    nOcurrenciasArbolSubconjuntos :: [Int] -> [Int] -> Int
    nOcurrenciasArbolSubconjuntos ys xs
     | xs == ys  = 1
     | otherwise = nOcurrencias ys (arbolSubconjuntos xs)
     
    nOcurrencias :: [Int] -> Arbol -> Int
    nOcurrencias ys (N xs zss) 
      | iguales ys xs = 1 + sum [nOcurrencias ys zs | zs <- zss]
      | otherwise     = sum [nOcurrencias ys zs | zs <- zss]
     
    subconjunto :: Eq a => [a] -> [a] -> Bool
    subconjunto xs ys = all (`elem` ys) xs
     
    iguales :: Eq a => [a] -> [a] -> Bool
    iguales xs ys = subconjunto xs ys &&  subconjunto ys xs
     
    prop_subconjunto :: Int -> [Int] -> Property
    prop_subconjunto n xs =
      elem xs (subsequences [1..n]) && n > 0 ==>
      nOcurrenciasArbolSubconjuntos xs [1..n] == factorial (n- length xs)
     
    factorial :: Int -> Int
    factorial x = product [1..x]
  5. javmarcha1
    import Data.List (permutations, subsequences)
    import Test.QuickCheck
     
    data Arbol = N [Int] [Arbol]
      deriving (Eq, Show)
     
    arbolSubconjuntos :: [Int] -> Arbol
    arbolSubconjuntos xs =
      N xs (map arbolSubconjuntos (maximales xs))
     
    maximales :: [Int] -> [[Int]]
    maximales xs =
      reverse [ys | ys <- subsequences xs, length ys == length xs - 1] 
     
    nOcurrenciasArbolSubconjuntos :: [Int] -> [Int] -> Int
    nOcurrenciasArbolSubconjuntos ys xs = aparece ys (todos xs)
     
    aparece :: [Int] -> [[Int]] -> Int
    aparece ys [] = 0
    aparece ys (xs:xss)
      | ys == xs  = 1 + aparece ys xss
      | otherwise = aparece ys xss
     
    todos :: [Int] -> [[Int]]
    todos xs = [ys | ys <- concat (todosmaximales [xs]), length ys < 2]
               ++ permutaciones [xs]
               ++ permutations xs
     
    todosmaximales :: [[Int]] ->[[[Int]]]
    todosmaximales [] = []
    todosmaximales xss =
      map maximales xss ++ todosmaximales (concat (map maximales xss))
     
    permutaciones :: [[Int]] -> [[Int]]
    permutaciones xss =
      concat [permutations ys
             | ys <- [xs | xs <- concat (todosmaximales xss)
                         , length xs > 1]]
     
    prop_arbolSubconjuntos :: Int -> Property
    prop_arbolSubconjuntos n  =
      n > 0 ==>
      and [ nOcurrenciasArbolSubconjuntos ys [1..n] ==
            product [1..n - length ys]
          | ys <- todos [1..n]]
     
    --   λ> quickCheckWith (stdArgs {maxSize=6}) prop_arbolSubconjuntos
    --   +++ OK, passed 100 tests.

Escribe tu solución

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