Menu Close

Relaciones arbóreas

Como se explica en el ejercicio Relación definida por un árbol, cada árbol binario define una relación binaria donde un elemento x está relacionado con y si x es el padre de y.

Una relación binaria es arbórea si

  • hay exactamente un elemento que no tiene ningún (la raíz del árbol) y
  • todos los elementos tienen dos hijos (los nodos internos) o ninguno (las hojas del árbol).

Definir la función

   arborea :: Eq a => [(a,a)] -> Bool

tal que (arborea r) se verifica si la relación r es arbórea. Por ejemplo,

   arborea [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)]  ==  True
   arborea [(8,3),(8,5),(10,2),(2,2),(2,0)]         ==  False
   arborea [(10,8),(8,3),(8,5),(10,2),(8,2),(2,0)]  ==  False

Soluciones

import Data.List ((\\), elemIndices, isPrefixOf, nub, sort)
 
-- 1ª solución
-- ===========
 
arborea :: Eq a => [(a,a)] -> Bool
arborea r =
  length [x | x <- nodos r, null (padres r x)] == 1 &&
  all (`elem` [0,2]) [length (hijos r x) | x <- nodos r]
 
-- (nodos r) es el conjunto de los nodos de la relación r. Por ejemplo,   
--    λ> nodos [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)]
--    [10,8,3,5,2,0]
nodos :: Eq a => [(a,a)] -> [a]
nodos r = nub (concat [[x,y] | (x,y) <- r])
 
-- (padres r x) es la lista de los padres de x en la relación r. Por
-- ejemplo, 
--    padres [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] 8   ==  [10]
--    padres [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] 10  ==  []
padres :: Eq a => [(a,a)] -> a -> [a]
padres r x = [y | (y,x') <- r, x' == x]
 
-- (hijos r x) es la lista de los hijos de x en la relación r. Por
-- ejemplo, 
--    hijos [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] 10  ==  [8,2]
--    hijos [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)] 5   ==  []
hijos :: Eq a => [(a,a)] -> a -> [a]
hijos r x = [y | (x',y) <- r, x' == x]
 
-- 2ª solución
-- ===========
 
arborea2 :: Eq a => [(a,a)] -> Bool
arborea2 xs =  length (nub padres \\ nub hijos) == 1
            && and [cuenta x padres == 2 | x <- nub padres]
  where
    (padres, hijos) = unzip xs
 
-- (cuenta x ys) es el número de ocurrencias de x en ys. Por ejemplo,
--    cuenta 7 [7,2,7,7,5]  ==  3
cuenta :: Eq a => a -> [a] -> Int
cuenta i = length . elemIndices i
Medio

3 soluciones de “Relaciones arbóreas

  1. agumaragu1
     
    import Data.List ((\))
     
    arborea :: Eq a => [(a,a)] -> Bool
    arborea xs = length (ys \ (zs++zs)) == 2 && all even (cuenta ys)
      where (ys,zs) = unzip xs
     
     
    cuenta :: Eq a => [a] -> [Int]
    cuenta [] = []
    cuenta (a:bs) = length as : cuenta (bs \ as)
      where as = [x | x <- (a:bs), x == a]
  2. Chema Cortés
    import           Data.List (elemIndices, nub, (\))
     
    count :: Eq a => a -> [a] -> Int
    count i = length . elemIndices i
     
    arborea :: Eq a => [(a,a)] -> Bool
    arborea xs =  length (nub padres \ nub hijos) == 1
               && and [count x padres == 2 | x <- nub padres]
      where
        (padres, hijos) = unzip xs
  3. angruicam1

    Una solución que creo sirve para cualquier árbol (se repita o no la raíz o cualquier elemento).

    import Data.List       (nub)
    import Data.List.Utils (countElem)
     
    arborea :: Eq a => [(a,a)] -> Bool
    arborea r =
      length raices <= 1
      && length (filter ((>) . fst <*> snd)
                 [(length ys,2*(countElem x h))
                 | (x,ys) <- relaciones]) <= 1
      && all even [countElem x p | x <- np]
      where (p,h)      = unzip r
            np         = nub p
            raices     = [x | x <- np, x `notElem` h]
            relaciones =
              [(x,ys) | x <- np, let ys = [y | (z,y) <- r, z == x]]

    Para comprobar la función podemos usar la función relacionDelArbol (definida en Relación definida por un árbol) y un generado de árboles y definir la propiedad de que toda relación dada por un árbol debe ser arbórea.

    import Control.Monad
    import Test.QuickCheck
     
    data Arbol a = H a
                 | N a (Arbol a) (Arbol a)
      deriving (Eq, Show)
     
    -- Propiedad
    -- =========
     
    -- La propiedad es
    prop_arborea :: Arbol Int -> Bool
    prop_arborea = arborea . relacionDelArbol
     
    relacionDelArbol :: Arbol a -> [(a,a)]
    relacionDelArbol (N a i@(N b _ _) (H c))       =
      (a,b) : relacionDelArbol i ++ [(a,c)]
    relacionDelArbol (N a (H b)       d@(N c _ _)) =
      (a,b) : (a,c) : relacionDelArbol d
    relacionDelArbol (N a i@(N b _ _) d@(N c _ _)) =
      (a,b) : relacionDelArbol i
      ++ (a,c) : relacionDelArbol d
    relacionDelArbol (N a (H b)       (H c))       =
      [(a,b),(a,c)]
    relacionDelArbol _                             = []
     
    -- La comprobación es
    --    λ> quickCheck prop_arborea
    --    +++ OK, passed 100 tests.
     
    -- Generador
    -- =========
     
    instance Arbitrary a => Arbitrary (Arbol a) where
      arbitrary = sized arbol
        where
          arbol 0       = liftM H arbitrary 
          arbol n | n>0 = oneof [liftM H arbitrary,
                                 liftM3 N arbitrary subarbol subarbol]
                          where subarbol = arbol (div n 2)
          arbol _       = error "Imposible"

    También podemos definir otra propuesta que sirve exclusivamente para árboles con padres como suma de hijos, como el del ejemplo, pero con un código bastante más simple.

    import Data.Map (toList, fromListWith)
     
    arborea :: (Num a, Ord a) => [(a,a)] -> Bool
    arborea =
      all ((==) . fst <*> snd)
      . toList
      . fromListWith (+)

Escribe tu solución

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