Árbol de subconjuntos

Definir las siguientes funciones

   arbolSubconjuntos       :: [a] -> Tree [a]
   nNodosArbolSubconjuntos :: Integer -> Integer
   sumaNNodos              :: Integer -> Integer

arbolSubconjuntos :: [a] -> Tree [a]

nNodosArbolSubconjuntos :: Integer -> Integer

sumaNNodos :: Integer -> Integer

tales que

(arbolSubconjuntos xs) es el árbol de los subconjuntos de xs. Por ejemplo.

     λ> putStrLn (drawTree (arbolSubconjuntos "abc"))
     abc
     |
     +- bc
     |  |
     |  +- c
     |  |
     |  `- b
     |
     +- ac
     |  |
     |  +- c
     |  |
     |  `- a
     |
     `- ab
        |
        +- b
        |
        `- a

λ> putStrLn (drawTree (arbolSubconjuntos "abc"))

abc

+- bc

| |

| +- c

| |

| `- b

+- ac

| |

| +- c

| |

| `- a

`- ab

+- b

`- a

(nNodosArbolSubconjuntos xs) es el número de nodos del árbol de xs. Por ejemplo

     nNodosArbolSubconjuntos "abc"  ==  10
     nNodosArbolSubconjuntos [1..4*10^4] `mod` (7+10^9) == 546503960

1 2	nNodosArbolSubconjuntos "abc" == 10 nNodosArbolSubconjuntos [1..4*10^4] `mod` (7+10^9) == 546503960

(sumaNNodos n) es la suma del número de nodos de los árboles de los subconjuntos de [1..k] para 1 <= k <= n. Por ejemplo,

     λ> sumaNNodos 3  ==  14
     sumaNNodos (4*10^4) `mod` (7+10^9)  ==  249479844

1 2	λ> sumaNNodos 3 == 14 sumaNNodos (4*10^4) `mod` (7+10^9) == 249479844

Soluciones

import Data.List (genericLength, genericTake)
import Data.Tree (Tree (Node))

-- Definición de arbolSubconjuntos
-- ===============================

arbolSubconjuntos :: [a] -> Tree [a]
arbolSubconjuntos [x] = Node [x] []
arbolSubconjuntos xs =
  Node xs (map arbolSubconjuntos (sinUno xs))

-- (sinUno xs) es la lista obtenidas eliminando un elemento de xs. Por
-- ejemplo, 
--    sinUno "abcde"  ==  ["bcde","acde","abde","abce","abcd"]
sinUno :: [a] -> [[a]]
sinUno xs =
  [ys ++ zs | n <- [0..length xs - 1]
            , let (ys,_:zs) = splitAt n xs]       

-- 1ª definición de nNodosArbolSubconjuntos
-- ========================================

nNodosArbolSubconjuntos :: [a] -> Integer
nNodosArbolSubconjuntos =
  fromIntegral . length . arbolSubconjuntos 

-- 2ª definición de nNodosArbolSubconjuntos
-- ========================================

nNodosArbolSubconjuntos2 :: [a] -> Integer
nNodosArbolSubconjuntos2 = aux . genericLength
  where aux 1 = 1
        aux n = 1 + n * aux (n-1)

-- 3ª definición de nNodosArbolSubconjuntos
-- ========================================

nNodosArbolSubconjuntos3 :: [a] -> Integer
nNodosArbolSubconjuntos3 xs =
  sucNNodos !! (n-1)
  where n = length xs

-- sucNNodos es la sucesión de los números de nodos de los árboles de
-- los subconjuntos con 1, 2, ... elementos. Por ejemplo.
--    λ> take 10 sucNNodos
--    [1,3,10,41,206,1237,8660,69281,623530,6235301]
sucNNodos :: [Integer]
sucNNodos =
  1 : map (+ 1) (zipWith (*) [2..] sucNNodos)

-- Comparación de eficiencia de nNodosArbolSubconjuntos
-- ====================================================

--    λ> nNodosArbolSubconjuntos 10
--    6235301
--    (9.66 secs, 5,491,704,944 bytes)
--    λ> nNodosArbolSubconjuntos2 10
--    6235301
--    (0.00 secs, 145,976 bytes)
--
--    λ> length (show (nNodosArbolSubconjuntos2 (4*10^4)))
--    166714
--    (1.07 secs, 2,952,675,472 bytes)
--    λ> length (show (nNodosArbolSubconjuntos3 (4*10^4)))
--    166714
--    (1.53 secs, 2,959,020,680 bytes)

-- 1ª definición de sumaNNodos
-- ===========================

sumaNNodos :: Integer -> Integer
sumaNNodos n =
  sum [nNodosArbolSubconjuntos [1..k] | k <- [1..n]]

-- 2ª definición de sumaNNodos
-- ===========================

sumaNNodos2 :: Integer -> Integer
sumaNNodos2 n =
  sum [nNodosArbolSubconjuntos2 [1..k] | k <- [1..n]]

-- 3ª definición de sumaNNodos
-- ===========================

sumaNNodos3 :: Integer -> Integer
sumaNNodos3 n =
  sum (genericTake n sucNNodos)

-- Comparación de eficiencia de sumaNNodos
-- =======================================

--    λ> sumaNNodos 10 `mod` (7+10^9)
--    6938270
--    (16.00 secs, 9,552,410,688 bytes)
--    λ> sumaNNodos2 10 `mod` (7+10^9)
--    6938270
--    (0.00 secs, 177,632 bytes)
-- 
--    λ> sumaNNodos2 (2*10^3) `mod` (7+10^9)
--    851467820
--    (2.62 secs, 4,622,117,976 bytes)
--    λ> sumaNNodos3 (2*10^3) `mod` (7+10^9)
--    851467820
--    (0.01 secs, 8,645,336 bytes)

100

101

102

103

104

import Data.List (genericLength, genericTake)

import Data.Tree (Tree (Node))

-- Definición de arbolSubconjuntos

-- ===============================

arbolSubconjuntos :: [a] -> Tree [a]

arbolSubconjuntos [x] = Node [x] []

arbolSubconjuntos xs =

Node xs (map arbolSubconjuntos (sinUno xs))

-- (sinUno xs) es la lista obtenidas eliminando un elemento de xs. Por

-- ejemplo,

-- sinUno "abcde" == ["bcde","acde","abde","abce","abcd"]

sinUno :: [a] -> [[a]]

sinUno xs =

[ys ++ zs | n <- [0..length xs - 1]

, let (ys,_:zs) = splitAt n xs]

-- 1ª definición de nNodosArbolSubconjuntos

-- ========================================

nNodosArbolSubconjuntos :: [a] -> Integer

nNodosArbolSubconjuntos =

fromIntegral . length . arbolSubconjuntos

-- 2ª definición de nNodosArbolSubconjuntos

-- ========================================

nNodosArbolSubconjuntos2 :: [a] -> Integer

nNodosArbolSubconjuntos2 = aux . genericLength

where aux 1 = 1

aux n = 1 + n * aux (n-1)

-- 3ª definición de nNodosArbolSubconjuntos

-- ========================================

nNodosArbolSubconjuntos3 :: [a] -> Integer

nNodosArbolSubconjuntos3 xs =

sucNNodos !! (n-1)

where n = length xs

-- sucNNodos es la sucesión de los números de nodos de los árboles de

-- los subconjuntos con 1, 2, ... elementos. Por ejemplo.

-- λ> take 10 sucNNodos

-- [1,3,10,41,206,1237,8660,69281,623530,6235301]

sucNNodos :: [Integer]

sucNNodos =

1 : map (+ 1) (zipWith (*) [2..] sucNNodos)

-- Comparación de eficiencia de nNodosArbolSubconjuntos

-- ====================================================

-- λ> nNodosArbolSubconjuntos 10

-- 6235301

-- (9.66 secs, 5,491,704,944 bytes)

-- λ> nNodosArbolSubconjuntos2 10

-- 6235301

-- (0.00 secs, 145,976 bytes)

-- λ> length (show (nNodosArbolSubconjuntos2 (4*10^4)))

-- 166714

-- (1.07 secs, 2,952,675,472 bytes)

-- λ> length (show (nNodosArbolSubconjuntos3 (4*10^4)))

-- 166714

-- (1.53 secs, 2,959,020,680 bytes)

-- 1ª definición de sumaNNodos

-- ===========================

sumaNNodos :: Integer -> Integer

sumaNNodos n =

sum [nNodosArbolSubconjuntos [1..k] | k <- [1..n]]

-- 2ª definición de sumaNNodos

-- ===========================

sumaNNodos2 :: Integer -> Integer

sumaNNodos2 n =

sum [nNodosArbolSubconjuntos2 [1..k] | k <- [1..n]]

-- 3ª definición de sumaNNodos

-- ===========================

sumaNNodos3 :: Integer -> Integer

sumaNNodos3 n =

sum (genericTake n sucNNodos)

-- Comparación de eficiencia de sumaNNodos

-- =======================================

-- λ> sumaNNodos 10 `mod` (7+10^9)

-- 6938270

-- (16.00 secs, 9,552,410,688 bytes)

-- λ> sumaNNodos2 10 `mod` (7+10^9)

-- 6938270

-- (0.00 secs, 177,632 bytes)

-- λ> sumaNNodos2 (2*10^3) `mod` (7+10^9)

-- 851467820

-- (2.62 secs, 4,622,117,976 bytes)

-- λ> sumaNNodos3 (2*10^3) `mod` (7+10^9)

-- 851467820

-- (0.01 secs, 8,645,336 bytes)

2 Comentarios

import Data.List  (genericLength)
import Data.Tree  (Tree, drawTree, unfoldTree)
import Data.Array (listArray, (!))

arbolSubconjuntos :: [a] -> Tree [a]
arbolSubconjuntos =
  unfoldTree
  (\ys -> if length ys == 1
    then (ys,[])
    else (ys,[as ++ drop 1 bs | n <- [0..length ys - 1],
              let (as,bs) = splitAt n ys]))

nNodosArbolSubconjuntos :: [a] -> Integer
nNodosArbolSubconjuntos xs = v ! n
  where v = listArray (0,n) (0:[i*v!(i-1)+1 | i <- [1..n]])
        n = genericLength xs

sumaNNodos :: Integer -> Integer
sumaNNodos n = snd (v ! n)
  where v = listArray (0,n)
        ((0,0):[(k,snd w + k) | i <- [1..n],
                let w = v!(i-1), let k = i*(fst w)+1])

import Data.List (genericLength)

import Data.Tree (Tree, drawTree, unfoldTree)

import Data.Array (listArray, (!))

arbolSubconjuntos =

unfoldTree

(\ys -> if length ys == 1

then (ys,[])

else (ys,[as ++ drop 1 bs | n <- [0..length ys - 1],

let (as,bs) = splitAt n ys]))

nNodosArbolSubconjuntos xs = v ! n

where v = listArray (0,n) (0:[i*v!(i-1)+1 | i <- [1..n]])

n = genericLength xs

sumaNNodos n = snd (v ! n)

where v = listArray (0,n)

((0,0):[(k,snd w + k) | i <- [1..n],

let w = v!(i-1), let k = i*(fst w)+1])

Responder

Una alternativa a nNodos usando las pilas.

import I1M.Pila (cima, apila, vacia)

nNodosArbolSubconjuntos :: [a] -> Integer
nNodosArbolSubconjuntos xs = cima (f 1 xs (apila 0 vacia))
  where f n (_:xs) p = f (n+1) xs (apila (n*(cima p)+1) p)
        f _ _      p = p

import I1M.Pila (cima, apila, vacia)

nNodosArbolSubconjuntos xs = cima (f 1 xs (apila 0 vacia))

where f n (_:xs) p = f (n+1) xs (apila (n*(cima p)+1) p)

f _ _ p = p

Árbol de subconjuntos

Soluciones

2 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

2 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico