Menu Close

Árbol de subconjuntos

José A. Alonso,

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

Medio
, , , , , , , , , , , ,

5 soluciones de “Árbol de subconjuntos”

  1. Responder
    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. Responder
    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. Responder
    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. Responder
    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. Responder
    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.